P=NP?

This lecture is an informal introduction to the P=NP question in computer science: are nondeterministic polynomial time problems (NP) the same as polynomial time problems (P)? We describe what these terms mean, give a brief history, and examine some of the arguments for and against this question.

The book mentioned is "Computers and intractability A guide to the theory of NP-completeness" by Michael R. Garey and David S. Johnson, which is recommended for further reading.

Correction: Kyla should be Kayal (in the Agrawal-Kayal-Saxena primality test).

[jstone]

"Huge amount of ingenuity and timewasting that goes into this competition" 😂👍

[SaveSoilSaveSoil]

I didn't expect this lecture to be so humorous and burst into laughter a few times. Thank you very much professor!

[chrislombardi]

These lectures are a great gift. Please continue!

[constantijndekker]

Hugely insightful lecture. For a time I always got the impression that P = NP was about wether every problem was solvable in polynomial time or something, and I didn’t really understand how P = NP can be proven by proving something like this in just one particular case, but now I (almost?) get it :)

[oskuh.]

Another absolutely great lecture that really helps to understand these concepts. Awesome!

[k-theory]

Thanks! Didn't know about the results depending on certain choice of oracles before, very cool!

[jhwaltjim]

Fabulous lecture, clear, organized, and amusing.

[varunachar]

I'm a big fan of all your content. Here I'll take the liberty to pick a tiny bone with you: you often speak of "solving algorithms", and of complexity classes as though they were a classification of *algorithms*. But really, they classify *problems*. A problem can usually be solved by more than one algorithm. The really important question is whether there exists (and if it does, how do we find) an algorithm that is fast. If there is a fast algorithm, that then puts the problem in one of the "fast" classes.

[shantshahbazian]

Very interesting and insightful lecture. It gets better and better as it goes on....

[alicewyan]

These lectures are a pleasure to watch! Would the V=L topic be suitable for an informal lecture like this one?

[robshaw]

I think nonstandard analysis can help here…. The reciprocal of a nonstandard infinitesimal is “finite but unbounded”, in nonstandard computer science, the exponent of the algorithm is similarly “finite but unbounded”…. So, if your Turing machine can run that long, it can solve NP problems in nonstandard polynomial time.

[zubin]

1:43 This is a minor nitpick, but I think the question "Does it factor?" at the beginning of the video should really be "What is its factorization?". The former is solvable in polynomial time, as you mention at 10:48, via the AKS primality test. The latter, as you also mention, is not known to be solvable in polynomial time.

[jamesfortune]

I'd say that a special case where N = NP are problems where you use the method that's used to check the answer to solve the problem. 😊

[danielpehoushek]

p=np for modest sizes. np=conp=pspace=#p=#q=qspace. avoid negation and prosper in truth. #P=#Q is in Knuth Volume 4.

[StatelessLiberty]

The thing about humans being able to produce long proofs got me thinking. Because if P≠NP and humans can do this, then somehow the human mind must be non-computational. I have heard Roger Penrose promoting a similar idea.

[abhishekkhetan]

Hi Professor. At 11:40 It is Agrawal, *Kayal*, and Saxena.

[danielvanbelgie]

Thank you professor, very interesting

[Searcher]

My comments:2) it exist models, I know they exist because I found some, that are like what is in nature, but they just approche the exponential time, what is not surprising because the limite for polinomials when approaching infinity is the exposentiel.12june2022.The real Sheldon.

[Searcher]

My comments: 1)computer are linear, that’s a big problem, because The (Mother) Nature has chosen to run things simultaniousely, both in atomic(and sub-atomic) level and as well in everything what is alive (including the brain). That means 2^n is prevalent.12 june 2022.The real Sheldon :-)

[neilruston]

Brilliant video - very enjoyable. The US spelling [color] hurt just a little ;)