P=NP?

[@jstone98]

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

[@brendawilliams8062]

I just say 100169

[@brendawilliams8062]

The quickest is 35 and 10012915

[@SaveSoilSaveSoil]

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

[@chrislombardi3968]

These lectures are a great gift. Please continue!

[@jhwaltjim]

Fabulous lecture, clear, organized, and amusing.

[@constantijndekker8343]

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.9577]

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

[@varunachar87]

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.

[@k-theory8604]

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

[@shantshahbazian9116]

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

[@robshaw2639]

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.

[@jamesfortune243]

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. 😊

[@alicewyan]

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

[@richarde.borcherds7998]

This would be a great topic for a lecture, but it will probably be soem time before I get around to set theory.

[@alicewyan]

@@richarde.borcherds7998 if it ever happens, I'll be looking forward to it :)

[@saniap234]

@@richarde.borcherds7998If you can make lecture series on Sets and Logic, for undergraduate level, it will be helpful.

[@roys4244]

@@richarde.borcherds7998 It would also be possible to add some set theory and logic links to the P-NP topic, in that course. I believe links have been claimed with Godel Incompleteness or ZFC expressiveness and the NP problem.

[@danielpehoushek2823]

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

[@zubin8010]

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.

[@TheEternalVortex42]

For NP it needs to be a yes/no problem, so you could change it to "does it have a factor

[@danielvanbelgie5807]

Thank you professor, very interesting

[@WesternTelecom]

Thanks professor!

[@abhishekkhetan]

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

[@richarde.borcherds7998]

Thanks; I'm not sure how that happened.

[@Searcher123456789]

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.

[@DreamzAnimation]

Thanks!

[@dra4lol]

Thank you for another great video

[@Searcher123456789]

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 :-)

[@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.

[@TheEternalVortex42]

I think a better take would be that humans focus only on the problems that are easy. There are so many unsolved problems in math after all.

[@magnuswootton7368]

computing is infinite.

[@ceoofthen-word8849]

Sweet!

[@neilruston8796]

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

[@ayadav4714]

Dear Professor, Would it not be better if the problem is tackled with respect to energy expended to solve P and NP Problems? It would be a more standard and general parameter to assess the various problems. Energy itself is linked with time by Einstein's relativity theory.

[@roys4244]

One issue with this energy idea is the need to find a "machine model" for the NP part. The P part has a Turing Machine, but the NP part has a "guessing" part - so what is the energy of that? Same question for the Oracle's which must differ somehow fundamentally.

[@migarsormrapophis2755]

Yee=NYee

[@brendawilliams8062]

I would put my money on you. Thx.

[@penekatehuatahi1347]

solved. P=peneka. NP=nau-peneka. next...