Beyond Computation: The P vs NP Problem - Michael Sipser 

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

German native speaker here: 28:37. He says: "Blosses Probieren". Means "only trying". FYI...

You would think that the Clay Institute and Harvard could afford an HD video camera.....

mad powerpoint skillz

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 RU-vid 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!

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.

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.

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

admiring a professor like dr Sipser: knowing everything is known about math and machines and forgetting that he wears a mic

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!

Where can I find the transformer which can transform factoring problem to clique problem?

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

Excellent lecture.

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?

**NP-complete decision problem:** Given a value for X, determine whether there exist integers A and B such that: * A - B = X * B = ln(A) This problem is NP-complete because it is a special case of the subset sum problem, which is a known NP-complete problem. **Reduction from subset sum problem:** Given a set of integers S and a target integer T, the subset sum problem is to determine whether there exists a subset of S that sums to T. We can reduce the subset sum problem to the NP-complete decision problem as follows: 1. Let S = {a1, a2, ..., an} be the set of integers and T be the target integer. 2. Create a new integer X = T + 1. 3. Determine whether there exist integers A and B such that: ``` * A - B = X * B = ln(A) ``` If there exist integers A and B that satisfy these conditions, then there exists a subset of S that sums to T. This is because we can set A = T + 1 + sum(subset) and B = ln(A), where subset is the subset of S that sums to T. Conversely, if there do not exist integers A and B that satisfy these conditions, then there does not exist a subset of S that sums to T. Therefore, the NP-complete decision problem is NP-complete. In this case, the decision problem of finding the values of A and B that satisfy the equation A - B = 4 and B = ln(A), where A and B are integers, is NP-complete. However, there do not exist any integers that satisfy this equation. Therefore, we can conclude that P does not equal NP. This is a very important result in computer science, and it has many implications for the field. For example, it means that there are some problems that cannot be solved efficiently by any computer, no matter how powerful.

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.

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?

It's a shame how few views this video has.

Good talk. Wish it went into more technical detail but overall was interesting.

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.

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?

16 years later, still unsolved.

Do quantum computing guys make any claims of addressing these P vs NP type computational complexity questions?

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

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'

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

All right, but doesn't it depend a lot how strong the computer is? How many flops? CPU speed?

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)

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 ?

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 ?

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)

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.

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.

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. ¿?

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?

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.

Did Sisper really use comic sans as the font for his lecture. oh dear

I came to this video to see an educational discussion on RU-vid in the comments section.

wonderfull !

Mr. Ardis sent me here.

it's a shame to see comic sans at such a venue

He is superb))))

Apparently RSA factoring challenges have been withdrawn. So, no money fellas !

I genuinely gasped in horror when I saw the comic sans. Other than that a fantastic lecture.

I mean proving p=np or p!=np would both be a tremendous achievement.

We need Category theory to answer the P vs NP problem.

Starts at 3:02

14 years later the P vs NP still not solved

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

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

It probably isn't but it would be the best discovery in human history if it actually is.

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.

Jordan didn't say he expected to to have more, just that it is a shame that it doesn't.

Would be interesting to see the mathematical proof for the theorem at 37:31

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.

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.

Are quantum computers allowed? Or does this question only pertain to classical computers? P = NP might be true for a quantum computer.

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.

Yea.. I need to practice my math:(

ANYTHING IN COMIC SANS IS IMMEDIATELY QUESTIONABLE REALLY SIPSER... THAT IS THE FONT YOU FELT BEST REPRESENTED MATERIAL RELATED TO HIGHER-EDUCATION MATHS?

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.

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.

'Primality' moved from RP (Randomized Polynomial) space to P, not from NP to P.

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.

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

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.

7.02722 hours to find the needle

Perelman refused 1M $ :)

14:48 Fucking Magnets how do they work?

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?

The model is a Turing machine, a sort of ideal computer. So years, I would assume be solar years.

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.

P and NP work in different directions - it's like comparing different dimensions.

my answer is: yes you must search!

I can demonstrate NP = PM ( Perpetuom Mobile ) .

The 1 dislike is by a dude who thinks P= NP, tisk tisk

I came here to brush up on my elementary mathematics.

Has anyone solved the $30k problem?

NOPE... uh... or is it yep,. whatever. solvable, yes. at least sometimes.

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?

great talk. the host looks like boris johnson

11 years gone, still no solution to this problem. Where are you genius???

ummmmmm umm um "silence*

Genetic algorithm is evolution math is said to be the best idea EVER. He's asking for somthing better.

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.

Anyone else here from Elementary?

the answer is 2

COMIC SAAAAAAAAAANS

And God only knows how much money the attendees paid.

Just put a allien in it if you want to have more viewers. ;-)

Comic Sans ...

Oh yeah? What if p is zero, huh?

WHY COMIC SANS, WHY? :l

It's a 1 hour video on a topic considered boring by most. How many views do you expect it to have?