Beyond Computation: The P vs NP Problem - Michael Sipser
Вставка
- Опубліковано 22 лис 2011
- Beyond Computation: The P vs NP Problem
Michael Sipser, MIT
Tuesday, October 3, 2006 at 7:00 PM
Harvard University Science Center - Hall B
One Oxford Street, Cambridge, MA, 02138
In a remarkable 1956 letter, the great logician Kurt Gödel asked the famous mathematician and computer pioneer John von Neumann whether certain computational problems could be solved without resorting to brute force search.
www.claymath.org/public_lectur...
www.claymath.org/public_lectur...
I watched this at the beginning of my semester and I now watch it again at the end of it. Let me just say, it makes more sense now. :)
3:20 P vs NP is a problem in computer science and mathematics. It concerns the amount of time it takes to solve a problem on a computer. Some take a really long time. And we're not really sure why.
4:53 Illustrating the problem using multiplication and factorization.
8:13 Why is factoring so hard? We only know a brute force technique. Which takes many steps searching through an enormous search space.
10:23 CLIQUE problem. Finding particular complete subgraphs. Only a brute force technique exists for solving.
14:07 Needle in a haystack example. Is searching necessary? i.e. Bruteforce. What if there's an easier way? e.g. Use a magnet and searching becomes unnecessary. So is there a mathematical analogue for the factoring and clique problem?
17:02 The P vs NP question informally: "Can we solve search problems without searching?"
17:30 P = Polynomial time. Quickly solvable problems. NP = Nondeterministic polynomial time. Quickly checkable (not solvable) problems. Includes the search problems.
21:30 History of P vs NP. 1960's - Dawn of complexity theory.
33:45 Sometimes you can avoid searching. e.g. Testing primality.
38:32 NP-completeness: The problems in NP are linked to one another. If you find a way to solve one problem in NP you can immediately solve other NP problems. Then P would equal NP. This is done by transforming other NP problems into a similar form as the solved problem. e.g. Any NP problem can be converted to a clique problem.
46:30 How to prove P != NP ? Here's some ideas.
51:30 Will P vs NP ever be solved? We need new ideas to solve it.
54:00 Q&A Portion
"If you find a way to solve one problem in NP you can immediately solve other NP problems". Nope. It's correct only if we're talking about NP-complete problems.
Great summary nevertheless. Thanks!
@@user-rz1cy3lc7k If the "primality" problem was initially (before 2002) an NP problem, why don't we transform any other NP problem into a "primality problem". So I guess you are right, this is true only for NP-complete problems.
German native speaker here: 28:37. He says: "Blosses Probieren". Means "only trying". FYI...
mad powerpoint skillz
You would think that the Clay Institute and Harvard could afford an HD video camera.....
+oracleofottawa I think the culprit here is the uploader rather than those esteemed institutions !
This is the best introductory video I've seen on the P =? NP problem. It hits the major points and describes them in intuitive fashion. As an aside, it's very cool that testing for primes is now known to be polynomial, something figured out just 10 years ago.
We use Sipser's book in my Theory of Computation class. I thoroughly enjoyed this lecture, his humor, and light-heartedness, because I believe that helps bridge the gap with people who might otherwise be intimidated or put off by the potential complexity of these topics. Thanks for posting this video!
This is really a damn awesome lecture about the P-NP-problem, especially for those who haven't heard anything about it before. It's the best introduction in this topic I could find on the internet and it definitely helped me a lot. Many thanks to Michael Sipser for his great work and to the UA-cam channel! BTW: Although I am German I had no problems to follow and understand the video. To me, that proves again how great and easily understandable the video is!
Hello sir.
A very good lecture on P vs NP problems, I'm currently going through my BE final year.I'm fortunate that I got this lecture when I was in much need of it.Though I wasn't able to catch up till the end of the lecture, however, it certainly cleared my basics over P & NP problems.
thank you very much..
Nice talk:) His textbook is also pretty good. I used it for my CS theory course, and helped me a lot to get better understanding.
I was expecting to be lost and confused, but after watching this lecture I feel enlightened! Great work (despite the use of comic sans)!
Amazing lecture, he provided simple and understandable examples.
fantastic lecture!
Excellent lecture.
🎯 Key Takeaways for quick navigation:
03:22 🤖 The P vs NP problem explores whether certain computational problems can be solved quickly (P) or if searching is always necessary (NP).
08:00 🕵️ Factoring and clique problems are examples of NP problems where searching is typically required, and they are hard to solve on computers.
17:02 🤔 The P vs NP question asks if checking problems (NP) is equivalent to solving problems (P), which is still unresolved in mathematics.
21:33 📜 The P vs NP question dates back to the 1970s but was explored in a letter from Kurt Gödel to John von Neumann in 1956.
23:08 📝 Gödel's letter raised the question of whether there is an efficient way to determine whether certain mathematical statements are provable, which is at the core of the P vs NP problem.
26:23 📜 Gödel's letter explicitly states the P vs NP problem, framing it in terms of a machine's time needed to test mathematical statements for proofs of length N.
27:45 ⏰ Gödel's letter introduces the concept of "fee of n" representing the time a machine requires to test mathematical statements, a key element of the P vs NP question.
28:14 🤯 Gödel's letter remarkably formulates the P vs NP question, which has become a central problem in computer science and mathematics.
31:02 💰 The P vs NP problem is regarded as one of the great challenges in contemporary mathematics and computer science, with a million-dollar prize offered by the Clay Institute for its solution.
34:36 🔍 Testing if a number is prime, once considered a searching problem, can now be solved quickly using advanced algorithms rather than exhaustive searches.
39:01 🧩 NP-completeness reveals that certain problems, like the clique problem, are linked to others in NP, implying that solving one efficiently could solve them all.
44:29 🎛️ The P vs NP problem involves understanding and possibly limiting the computational power of algorithms to prove that some problems inherently require searching.
54:37 🧩 Some problems can be solved quickly if approximate solutions are acceptable. For example, approximate scheduling solutions can be found quickly.
55:42 🧩 Sudoku puzzles are NP-complete problems, meaning they are computationally challenging to solve.
56:32 🖥️ Distributed computing can simulate a problem that could be solved on a single processor, but for NP-complete problems, it doesn't significantly change the computational complexity.
58:03 📊 The difference between finding the largest clique and finding a clique of a specified size affects whether the problem is in NP or not. Both are closely related computational problems.
59:01 ❓ There is debate in the scientific community about whether the P vs. NP question may be one of those problems that cannot be resolved within the current mathematical axioms, akin to questions like the Continuum Hypothesis.
NP stand for Non-Deterministic Polynomial Time
Hey pal, did you know Schaefer Dichotomy Theorem?
Great lecture. Thanks alot.
Ive always thought the best way to describe the P=NP problem is to ask whether all problems, the answers to which are easily verifiable, are also easily solvable?
Good talk. Wish it went into more technical detail but overall was interesting.
admiring a professor like dr Sipser: knowing everything is known about math and machines and forgetting that he wears a mic
Awesome lecture. Looking for a clique of a certain number seems like a "Where's Waldo" type thing. How could you solve that without searching/with an algorithm? Seems impossible.
It uses "computer years" because it doesn't really matter what kind of unit of measure you use for the time, of what computer power you use. Put it simply, the point is that with P problems a slight change of "difficulty" in the inputs results in a slight change of processing time. With NP, the change is exponential, so even for a slight change in difficulty, you can get an ENORMOUS change in running time! That is true for any computer, being it a supercomputer or my crappy laptop
Is there a standardized unit of 'computer years' that he is using? It seems to me that it may differ a lot per computer, especially if you use multiple cores.
I really liked the talk. The CLIQUE problem is very interesting. What if the nodes are people and participate in solving the problem as opposed to an external observer trying find CLIQUEs ... as in some kind of broadcasting and receiving echo back?
How do you convert different problems to generic CLIQUE problems and how does that work?? I need to know this as the second ones don't seem so hard to find: just don't count circles wich have a few connections to begin with , then I have a few more ideas but that would depent on how the problem is converted.
To an extent, yes, but when you look at the size of real world problems - like finding the largest clique in Facebook's social graph of millions of users - the sheer size of the problem quickly makes even the fastest computers still incredibly slow compared to the search space involved. Even if you could do it in, say, a second using a super fast computer, you could STILL get a decrease in computation time of many orders of magnitude by solving one of these problems.
16 years later, still unsolved.
This video explains what are P and NP problem in much better and simpler way than any other sources on internet.
I still have one question though: when fast solution to the Primality problem was found ,which was a NP problem earlier , its category changed from NP to P but why could not we use those transformers(as shown in video) to transfer other problems into primality problem and solve other NP problems ?
Primality is not/never been NP-complete. Actually, it is in P now as you correctly state (AKS). No being NP-complete, no "transformer".
The "verification" process of a problem implies precomputed steps that would assert the truth value for that particular solution. In the case P = NP would imply that the verification steps contain solving steps of the problem, thus making the verification and solving algorithms identical and non realistic. Simply, one could tell that the verification algorithm may contain solving steps, but not vice-versa, thus NP problems will never execute in polynomial time (P /= NP)
Where can I find the transformer which can transform factoring problem to clique problem?
Because most people don't have any interest in problems like P = NP ? because it goes over their mind or they think that's boring and which is a very sad thing......
He is superb))))
Do quantum computing guys make any claims of addressing these P vs NP type computational complexity questions?
It's a shame how few views this video has.
40:30 the folks must be notice here is that not all NP problems were NP-Complete. There is also NP-Intermediate and pure NP problems (Non NP-Complete problems)
wonderfull !
Starts at 3:02
All right, but doesn't it depend a lot how strong the computer is? How many flops? CPU speed?
BTW, only NP-complete problems have the property of solving other NP problems in polynomial time if a polynomial time algorithm is found for the NP-complete problem.
You will still need to go through each node and check how many links it has. In other words, you're searching for nodes with a sufficient number of links, and then you're searching for a Clique within that pool.
Question about the 'Old Theorem a^(P-1) mod P == 1':
Why is there a=2 and not just a 2 in the equation ?
Is there a case you would like to use a other value for a'
The theorem says the equation holds for all a < p. So for instance, if p = 7, then we might use a = 3, for instance. In that case, we have 3^6 = 729. Now, 729 / 7 = 104 R 1, so 3^6 = 1 (mod 7). You could do the same for a = 4 (4^6 = 4096, 4096 / 7 = 585 R 1), a = 5, and a = 6.
I'm not quite sure if you'd ever want to use other numbers, but I can imagine it would be helpful in some way. If you want to test the primality of some very large numbers such as the large factorable one given by the RSA in this video, while 3^n >> 2^n, both are very, very large indeed, and if there's some kind of pattern of technique that can be used to your benefit for 3^n but not 2^n, then it would probably be beneficial to use the larger one.
Or, it could just be that since the theorem holds for all a
My knowlegde of mathematics is appallingly sparse, but conceptually I have to agree with you. I mean, how on earth can you search a field and simply know by searching that you have arrived at the correct answer for a given problem? Even if the field is of all possible primes... we don't even have an alg to effectively compute primes... *sigh* well, back to algebra and calc.
As Linear programming (LP) is categorized as a P-problem, can other problems that can be solved using LP (like scheduling) be categorized as P?
Scheduling problem cannot be solved by a LP, and it is np problem.
what if I can solve a Max clique problem having 50-70 nodes using my laptop in a week. Will it be any development for P vs NP problem?
Not necessarily. From my understanding, the issue of scaling is the predominant issue, not necessarily the result itself. If your solution consistently solved the Max Clique problem in polynomial time, then you'd have made an important discovery.
You will get a mathematical prize if you find a non brute force solution.
I genuinely gasped in horror when I saw the comic sans. Other than that a fantastic lecture.
Apparently RSA factoring challenges have been withdrawn. So, no money fellas !
Good point, but still it seems useful to have a useful metric other than 'computer years'. With the same logic, if you have a problem that takes 2 years to solve, and then a computer a thousand times faster comes along it becomes 2.5 months.
Did Sisper really use comic sans as the font for his lecture. oh dear
It is said that trying to crack AES-256 bit encryption by brute force could take upwards of 10^50 years for even the most powerful supercomputers to crack today.
So even if 1000 year from now they have computers that are a trillion trillion times faster than the ones today it will still take something like 10^26 years to crack AES-256 even with those newer faster supercomputers.
Solving problems in generic computing units makes it where you can simply multiply 2 numbers to get actual time.
Quantum computers will be doing this within a decade.
@@daddust True. But it is likely that they are already working on quantum encryption at the same time that will be unable to be cracked by a quantum computer. I wrote that post 7 years ago when I was still back in college taking a 400 level computer science class.
I remember reading the book my Michael Sipser and it was the hardest thing I have ever done. I don't remember any of it. So difficult.
pudiera medirse con matemáticas vectoriales como la de los poliedros en otra di mención multiplicado por el numero de posibles cara frac-tales dividido por el posible tiempo elevado a la masa del objeto. ¿?
Jordan didn't say he expected to to have more, just that it is a shame that it doesn't.
We need Category theory to answer the P vs NP problem.
Mr. Ardis sent me here.
I came to this video to see an educational discussion on UA-cam in the comments section.
Wouldn't the P/NP problem be related to Godel Incompleteness which says that within any formal system that can express arithmetic there are truths which cannot be proven within the system. Why doesn't that settle the problem in favor of P not equal NP ?
you mean that no one has shown that the clique problem is unsolvable? ok, but godel incompleteness says that every powerful formal system contains some unprovable theorems. so wouldn't those theorems be NP?
I think not. If a theorem is unprovable then it isn't checkable by a polynomial time algorithm to be true. So i think that would place that proof in EXPTIME.The proof that P!=EXPTIME acutually uses that logic and it was proved that you can't prove P vs NP using the same argument.
present numerical machine inadequate to address the problem . but a language machine huge parallel computation , arithmetic is being done through language. the Natural language is finitely specified, in either way traversing competency. it is language machine itself. that my work., it will address many problems that you have mentioned. if you are interested i will mail more details.
The model is a Turing machine, a sort of ideal computer. So years, I would assume be solar years.
'Primality' moved from RP (Randomized Polynomial) space to P, not from NP to P.
He felt like others had contributed to his proof in such a degree that he did not deserve all the credit (or something in those lines).
Why isn't P != NP changed to P != CP + NP;
Where CP = catalog and index.
Working on infinite data is then/always working on the current data set.
i have no idea.
Would be interesting to see the mathematical proof for the theorem at 37:31
+The Truthful Channel he said that you can try any number and send it through that theorem and see if it is prime or not he gave you the algorithm to test with see if its false for yourself
TheCykodude I know I can test it, but a mathematical proof is something very different.
It's known as Fermat's little theorem. You should be able to find it in elementary number theory books and internet sources easily. Basically the proof goes like this:
In a prime modulo, every nonzero element has a multiplicative inverse (i.e. if a=/=0 mod p, there is b such that ab=1 mod p). This is because the pair (a,p) would be relatively prime if p does not divide a (apply euclidean algorithm).
This means all of a, a^2, ..., a^p cannot be 0 mod p. There are p numbers in the list a, a^2,..., a^p, but there are only p-1 distinct nonzero members in modulo p. By the pigeonhole principle, there must be a^i, a^j in the list identical in modulo p. Set k=i-j so that a^k=a^(i-j).
Since a^i=a^j mod p, we get a^k=1 mod p. Now we show that k must divide p-1. Consider the nonzero elements 1, 2, ..., p-1. We can separate (partition) these elements by whether or not one can be obtained from another by keep multiplying a^k: let's say two members n, m in the list are related (written n~m) whenever n can be eventually obtained by keep multiplying a^k to m. This ~ is an equivalence relation: you can group the numbers in the list 1,2,...,p-1 by whether they are related or not. You will get exactly same number of members in each group, say t, and there will be total of k groups. So, t*k=p-1. Using the above fact that a^k=1 mod p, we get a^(p-1)=a^(tk)=1 mod p.
well it's fermat's theorem
the proof can be done in two steps using simple reccurency !
14 years later the P vs NP still not solved
at least factoring got proved to be P
P vs NP is a problem of algorithm we will never know. The best we can do is a trial and error method for the 'click' problem, taking a long time.
Godel didn't prove the incompleteness problem for finite axiom algorithm of mathematics, he proved it for infinite axiom algorithm of circular linguistic logic (the lying paradox or the barber paradox).
I mean proving p=np or p!=np would both be a tremendous achievement.
It seems that there is a mistake @ 0:28. "time is polynomial then the problem is NP, if time is more than polynomial then the problem is not NP." But i think this is wrong. if the time is polynomial then the problem is P, not NP. Who can explain this to me??? Thanks
it's a shame to see comic sans at such a venue
It probably isn't but it would be the best discovery in human history if it actually is.
Yea.. I need to practice my math:(
14:48 Fucking Magnets how do they work?
7.02722 hours to find the needle
The clique problem also seems like, "Find out where in the world lives a family of 5 people." How could you possibly find a family like that without searching or with a mathematical algorithm? That seems impossible.
I can demonstrate NP = PM ( Perpetuom Mobile ) .
sorry to say the RSA competitions are no longer active, though I'd say if you had a way of factoring those numbers efficiently you shouldn't be short on cash too long.
+mitchumsport hey mitch, can you tell me how I would make money if I figured out how to factor numbers?
+Dan McLittle think, digital bank robbery, information you could take from nearly any email account, etc. you would have undermined a critical/important encryption mechanism
+mitchumsport how would you do that?
+Dan McLittle I mean, If you had a way to get the prime factorization, how would you get the information from users.
All the bitcoin would be mine just before NSA commandos took me to the Antartic bunker.
The man asking about distributed computers completely misunderstood the problem. Increasing calculation speed is not the solution of complex problems because you still end up going into ridicukous computation time. Make your computer ten, a hundred, a million times faster and you still wont solve the problem in a rational time frame.
my answer is: yes you must search!
ANYTHING IN COMIC SANS IS IMMEDIATELY QUESTIONABLE
REALLY SIPSER... THAT IS THE FONT YOU FELT BEST REPRESENTED MATERIAL RELATED TO HIGHER-EDUCATION MATHS?
To put it another way, if you have a problem that takes millions of years to solve, and then a computer a thousand times faster comes along, then yes, you've reduced the time to "only" a thousand years - but is that really any practical difference?
Perelman refused 1M $ :)
The clique problem seems incredibly easy to create an algorithm for?
No need to check all possible combinations.
Number each point, and count the amount of connections that point has.
1:4
2:3
3:9
Or whatever, create a data point entry for each.
Then write down how each number connect to others.
1:4 ( 3, 5 11, 27 ) etc..
Then just search you database.
If you want max?
Point with largest amount of connections has N connections!
Is there N other points that has N connections?
No? Do N-1
Yes? Are they connected to each other?
No? do N-1
Yes? Max clique=N ( that should be quite easy to find in the grid. )
If there are several you just iterate.
Still a bit computing heavy, but say a thousand point grid would not require a DB larger then a couple of megabytes, and searchable within a narrow timescale, surely well below centuries?
From the top of my head, please correct me if I am wrong.
I might have said algorithm when that was not really what I meant.
You create a database of all points, with all information they can have, including number of connections, and you give each point a unique name.
Regardless of size, a computer could create that database fairly quickly.
Once you have that, you should be able to derive any information you want about that collection of points you could ever want.
But regardless, NP can never be P, as the amount of points can be infinite so will the computation time, even if it is not x^n.
P however will turn into NP as it grows.
Or so I assume! ;)
Glindin "The clique problem seems incredibly easy to create an algorithm for?"
It's relatively easy to implement, but it's still requires brute-force searching:
"Yes? Are they connected to each other?"
This is the problem. This is where the NP exponential time comes into play.
NOPE... uh... or is it yep,. whatever. solvable, yes. at least sometimes.
Are quantum computers allowed?
Or does this question only pertain to classical computers?
P = NP might be true for a quantum computer.
From what I understand the problem of P vs NP, as stated in this lecture, is whether one can avoid having to search (brute-force) the answer.
With a quantum computer you may be searching much faster, but you're still searching. Whether P=NP or not, the answer is the same for both classical and quantum.
Johnson Turing Yeah but quantum computers aren't just "faster computers", for most things they would be actually slower at than a classical computer. But for searching, they might be able to turn "nondeterministic polynomial time" problems into "polynomial time" problems. In that case, NP = P
Stephen Kamenar you're right in the sense that quantum computers may be able to solve some searching problems like factorization quickly. But those problems are not NP-complete, you can't reduce problems like the traveling salesman or clique to a factorization problem. So I think a quantum computer cannot help you in a general searching problem apart from making brute-search faster.
Johnson Turing I highly disagree, given the ability of a perfect quantum computer of really having and using q-bits units and by creating a q-bits mask of type prime that simultaneously satisfies the conditions extrapolated by the Fermat test or better another more powerful extensions of it, such as Miller-Rabin, Solovay-Strassen, or Baillie-PSW, finding all primes in a large set would be as simple and equally as fast as just feeding the large set of numbers (perhaps approximating to infinite) to the quantum computer, applying the mask to the set to immediately extract the resulting set of primes with just an AND cycle.
That is the all point of quantum computing: to find all solutions at once.
+Farzher
P and NP are defined in purely mathematical terms. No device that anybody could build or imagine changes anything about whether P is or is not equal to NP.
What you are looking for is probably something like BQP, which is a subset of NP and a superset of P and corresponds to quantum computers. You could ask if BQP=NP. That too is an open question.
On the other hand, if P=NP then BQP=NP because of the inclusion hierarchy. This also means that if BQP != NP then P != NP.
So is the P vs. NP problem a NP problem or a P problem?
Is anyone brute force searching for a solution for P vs. NP?
if you can test every single possible algorithm a computer can run and see if it solves the clique problem in a polynomial time, then you can solve the P vs NP problem as an NP problem. But you can't because the number of possibilities is not finite. So solving P vs NP is not even an NP problem let alone a P problem.
jidma So does that make it a non-NP problem? Would that be a non-nondeterministic polynomial or nondeterministic nonpolynomial?
mah brain herts!
Anyway thanks for answering.
P and NP work in different directions - it's like comparing different dimensions.
I came here to brush up on my elementary mathematics.
great talk. the host looks like boris johnson
Genetic algorithm is evolution math is said to be the best idea EVER. He's asking for somthing better.
Has anyone solved the $30k problem?
The 1 dislike is by a dude who thinks P= NP, tisk tisk
ummmmmm umm um "silence*
Anyone else here from Elementary?
And God only knows how much money the attendees paid.
the answer is 2
42
COMIC SAAAAAAAAAANS
11 years gone, still no solution to this problem. Where are you genius???
he should take a bet with someone that says "it will never be proven" the worst that can happen is both of you die before it's proven
PS: ignoring the fact someone proves it's non provable.
Comic Sans ...
Oh yeah? What if p is zero, huh?
And 'personal problems are evil'? What a way to disrespect someone's opinion, post modern dude.
WHY COMIC SANS, WHY? :l
One of the RSA presentations also uses Comic Sans. :)
Just put a allien in it if you want to have more viewers. ;-)
EU2K