P vs. NP: The Unsolvable(?) Computer Science Problem

Even though computers are able to draw and write poetry now, there are still unsolved problems in computer science. I'm not talking about unsolvABLE problems like the halting problem, but problems like the P vs. NP problem, which is probably solvable but a solution hasn't been found. Will you figure it out? If you do, you will win one million dollars. That is not a joke.

MUSIC USED:
Uptown Down from SimCity 3000
Gloam Valley from Super Paper Mario
Steam Gardens from Super Mario Odyssey
Beachside Dream from Mario and Luigi: Bowser's Inside Story
Dimble Woods Part II from Mario and Luigi: Bowser's Inside Story
Snow Kingdom from Paper Mario: Sticker Star
Itty Bitty 8 Bit by Kevin MacLeod
Bob-Omb Battlefield from Super Mario 64

VIDEO USED:

[patriciafergus]

Turtle: Bogo sort is the dumbest sorting algorithm

Quantum Bogo Sort: Exist in a superposition of holding my beer and not holding my beer

[LoFiAxolotl]

1974 i finished my PhD in math.... me and 14 of my colleagues were working on that problem all got matching P=NP tattoos on our arms... the amount of times i have had people ask if it's a gang of some sort... love it..

also glad that we made 0 steps in the last 50 years but the future looks promising! "AI" won't solve it but quantum computing seems to have some interesting approaches in finding solutions

[mm]

Miracle sorting is the best sorting algorithm, you just wait for the list to solve itself by some miracle

[larry_berry]

Thanks for an explanation. Yesterday I have been unsuccessfully trying to understand what P, NP, NP-complete and NP-hard mean for a lot of time and after watching this video I finally understood them.

[vicr]

Never thought I'd ever see Obfuscate break down

[gameofpj]

I think you have a small inaccuracy in the bogo sort time complexity. If you just shuffle without checking for duplicates, there isn't an upper limit, so even O(n!) isn't correct.

[Yvant]

Hey ! I love seeing this kind of video where you explain a complex concept in a simple way ! Thanks a lot !

[Gutagi]

I found a beatiful proof for P=NP, which this comment is to narrow to contain.

[svecs]

even better algorithm is Miracle Sort

check if the array is sorted and if not, wait and check again... eventually the radiation will flip the right bits and sort it

[Joker]

Hello from a Complexity Theorist! If you want to make a really unique video, check out the theory behind P-Completeness, characterized simply as "problems which generally can't be solved faster using parallel computation techniques using only polynomial processors".

[unchaynd]

On the subject of sorting algorithms, my personal favorite is sleepsort. It kind of... converts time complexity to space complexity.

[CrowJustin]

Here before Victor!
Also can’t help but notice that P and NP in 5:34 are from a series known as Alphabet lore.

[enoua]

I love watching these videos despite already having a good grasp on the concepts already, you make it so fun! Plus it could probably show them to my friends in lieu of rambling on to them about cs and mathematics that i think are cool

[dafoex]

I wonder how many people have asked GPTChat to solve P = NP
I wonder if its ever returned something useful.

[Izzythemaker]

Thanks for making this video. The other ones I saw never explained why NP-complete was a subcategory of NP and didn't even mention NP-hard

[StoryTeller]

Why not use Bogo to check for every single possible wrong answer that P =NP could produce? If it produces enough of them, P != NP, if it doesn't, P = NP

Oh, so that is why P = NP is so important. What if a fictional hacker character like Radical Edward from Cowboy Bebop or someone like them attempted to solve this problem. Or, what if this problem was already solved sometime in the year 2100 or around that time, maybe a few decades before, maybe a few decades after? What kind of future would humanity be living in?

[reinerczerwinski]

10:12 factorisation in in NP. but it is unlikely, that it is NP-complete. RSA could be cracked with quantum computer although there is no efficient quantum algorithm for NP-hard problems

[MrCheeze]

Are impossible problems like the halting problem actually considered NP-hard? I would have said no, and that time complexity is only an applicable concept to things that are actually computable.

[felixstuber]

Well even if P=NP is shown, it doesn't mean our encryption breaks over night. For once it might be a non-constructive proof, so we might know there must be an algorithm to factor large numbers in polynomial time but not what it was.

Also just because something can be solved in P-Time, doesn't mean it would be fast. Something like x⁹⁹⁹⁹⁹ is in P, but it still grows pretty fast.

[Rignchen]

4:50 hey, did you know about bogo bogo sort? it's basiclly bogo sort but worst (there's also quantum bogo sort but this one is actually the best algorythme ( =O(1) ), except it's not cause you can't use it)