Beyond Computation: The P vs NP Problem - Michael Sipser

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

Пікірлер: 152

  • @MubashirullahD
    @MubashirullahD5 жыл бұрын

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

  • @AlexandriaRohn
    @AlexandriaRohn8 жыл бұрын

    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

  • @user-rz1cy3lc7k

    @user-rz1cy3lc7k

    6 жыл бұрын

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

  • @user-rz1cy3lc7k

    @user-rz1cy3lc7k

    6 жыл бұрын

    Great summary nevertheless. Thanks!

  • @giorgosisb6977

    @giorgosisb6977

    Жыл бұрын

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

  • @Bierchen1337
    @Bierchen13376 жыл бұрын

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

  • @starry107
    @starry1079 жыл бұрын

    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!

  • @fredericjacob1993
    @fredericjacob199311 жыл бұрын

    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 KZread 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!

  • @chrimony
    @chrimony12 жыл бұрын

    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.

  • @oracleofottawa
    @oracleofottawa9 жыл бұрын

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

  • @thethakuri

    @thethakuri

    8 жыл бұрын

    +oracleofottawa I think the culprit here is the uploader rather than those esteemed institutions !

  • @user93237
    @user9323710 жыл бұрын

    mad powerpoint skillz

  • @entropy1
    @entropy110 жыл бұрын

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

  • @Max06504-e
    @Max06504-e5 жыл бұрын

    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.

  • @blondemaverick
    @blondemaverick11 жыл бұрын

    I was expecting to be lost and confused, but after watching this lecture I feel enlightened! Great work (despite the use of comic sans)!

  • @Mr1ncept10n
    @Mr1ncept10n11 жыл бұрын

    Amazing lecture, he provided simple and understandable examples.

  • @BELLAROSE21212
    @BELLAROSE21212Ай бұрын

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

  • @ytpah9823
    @ytpah98239 ай бұрын

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

  • @dororo2597

    @dororo2597

    9 ай бұрын

    NP stand for Non-Deterministic Polynomial Time

  • @dororo2597

    @dororo2597

    9 ай бұрын

    Hey pal, did you know Schaefer Dichotomy Theorem?

  • @marv4645
    @marv464510 жыл бұрын

    fantastic lecture!

  • @hajijohn1
    @hajijohn15 жыл бұрын

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

  • @Vidrinskas
    @Vidrinskas11 жыл бұрын

    Excellent lecture.

  • @masabhasnain8586
    @masabhasnain85867 жыл бұрын

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

  • @nickwalsh527
    @nickwalsh5273 ай бұрын

    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?

  • @Makeanimagination
    @Makeanimagination11 жыл бұрын

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

  • @aleksandar5323
    @aleksandar532311 жыл бұрын

    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.

  • @Pianofy
    @Pianofy10 жыл бұрын

    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.

  • @GarethHall
    @GarethHall10 жыл бұрын

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

  • @Vonzi0000
    @Vonzi000012 жыл бұрын

    Great lecture. Thanks alot.

  • @soxnation1000
    @soxnation100011 жыл бұрын

    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.

  • @AmitLangotex
    @AmitLangotex11 жыл бұрын

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

  • @ESEJERITO
    @ESEJERITO10 жыл бұрын

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

  • @Pianofy
    @Pianofy10 жыл бұрын

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

  • @ketancmaheshwari
    @ketancmaheshwari11 жыл бұрын

    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?

  • @dororo2597
    @dororo25979 ай бұрын

    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)

  • @spazneria
    @spazneria12 жыл бұрын

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

  • @scientious
    @scientious2 жыл бұрын

    16 years later, still unsolved.

  • @GiovanniSirioCarmantini
    @GiovanniSirioCarmantini10 жыл бұрын

    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

  • @leowong9438
    @leowong94387 жыл бұрын

    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?

  • @asgharmoeini55

    @asgharmoeini55

    4 жыл бұрын

    Scheduling problem cannot be solved by a LP, and it is np problem.

  • @Jackieception
    @Jackieception10 жыл бұрын

    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)

  • @rdormer
    @rdormer10 жыл бұрын

    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.

  • @masabhasnain8586
    @masabhasnain85867 жыл бұрын

    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?

  • @omfggoodwill1234

    @omfggoodwill1234

    7 жыл бұрын

    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.

  • @daddust

    @daddust

    3 жыл бұрын

    You will get a mathematical prize if you find a non brute force solution.

  • @ArbanUka
    @ArbanUka11 жыл бұрын

    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

  • @mallxs
    @mallxs10 жыл бұрын

    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'

  • @JnCrWe

    @JnCrWe

    10 жыл бұрын

    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.

  • @PeterGeras

    @PeterGeras

    10 жыл бұрын

    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

  • @ninodoko
    @ninodoko11 жыл бұрын

    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.

  • @dmk1913
    @dmk191311 жыл бұрын

    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 ?

  • @Ezop1959

    @Ezop1959

    4 жыл бұрын

    Primality is not/never been NP-complete. Actually, it is in P now as you correctly state (AKS). No being NP-complete, no "transformer".

  • @potugadu5160
    @potugadu516011 жыл бұрын

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

  • @potugadu5160
    @potugadu516011 жыл бұрын

    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.

  • @thethakuri
    @thethakuri8 жыл бұрын

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

  • @leighbee13
    @leighbee1311 жыл бұрын

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

  • @daddust
    @daddust3 жыл бұрын

    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.

  • @vasudevaraovadoothker5092
    @vasudevaraovadoothker50925 ай бұрын

    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.

  • @FarizaINDY
    @FarizaINDY11 жыл бұрын

    He is superb))))

  • @mallxs
    @mallxs10 жыл бұрын

    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.

  • @shipper66

    @shipper66

    10 жыл бұрын

    i have no idea.

  • @EinSofQuester
    @EinSofQuester8 жыл бұрын

    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 ?

  • @neiljohnson7914

    @neiljohnson7914

    7 жыл бұрын

    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?

  • @nlysts

    @nlysts

    6 жыл бұрын

    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.

  • @viliusposka2245
    @viliusposka22459 жыл бұрын

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

  • @SpartanOdyssey
    @SpartanOdyssey5 жыл бұрын

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

  • @H33t3Speaks
    @H33t3Speaks10 жыл бұрын

    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.

  • @naimulhaq9626
    @naimulhaq96264 жыл бұрын

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

  • @Muzikrazy213
    @Muzikrazy21311 жыл бұрын

    I came to this video to see an educational discussion on KZread in the comments section.

  • @simopr09
    @simopr0911 жыл бұрын

    wonderfull !

  • @stevelam5898
    @stevelam58987 ай бұрын

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

  • @thetruthfulchannel6348
    @thetruthfulchannel63488 жыл бұрын

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

  • @TheCykodude

    @TheCykodude

    8 жыл бұрын

    +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

  • @thetruthfulchannel6348

    @thetruthfulchannel6348

    8 жыл бұрын

    TheCykodude I know I can test it, but a mathematical proof is something very different.

  • @neutralcriticism4017

    @neutralcriticism4017

    7 жыл бұрын

    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.

  • @captainecarisma11

    @captainecarisma11

    7 жыл бұрын

    well it's fermat's theorem the proof can be done in two steps using simple reccurency !

  • @physira7551
    @physira75514 жыл бұрын

    14 years later the P vs NP still not solved

  • @NoNameAtAll2

    @NoNameAtAll2

    2 жыл бұрын

    at least factoring got proved to be P

  • @LeoMRogers
    @LeoMRogers10 жыл бұрын

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

  • @mmmmSmegma
    @mmmmSmegma9 жыл бұрын

    14:48 Fucking Magnets how do they work?

  • @Pianofy
    @Pianofy10 жыл бұрын

    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.

  • @ComatoseLife
    @ComatoseLife11 жыл бұрын

    Starts at 3:02

  • @soxnation1000
    @soxnation100011 жыл бұрын

    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.

  • @aq1q
    @aq1q11 жыл бұрын

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

  • @H33t3Speaks
    @H33t3Speaks10 жыл бұрын

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

  • @Ehatre
    @Ehatre8 жыл бұрын

    Mr. Ardis sent me here.

  • @elidrissii
    @elidrissii11 жыл бұрын

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

  • @astroboomboy
    @astroboomboy11 жыл бұрын

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

  • @GenericInternetter
    @GenericInternetter10 жыл бұрын

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

  • @brookesrook
    @brookesrook11 жыл бұрын

    7.02722 hours to find the needle

  • @bryanboone7363
    @bryanboone736310 жыл бұрын

    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.

  • @daddust

    @daddust

    3 жыл бұрын

    Quantum computers will be doing this within a decade.

  • @bryanboone7363

    @bryanboone7363

    3 жыл бұрын

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

  • @stephenkamenar
    @stephenkamenar10 жыл бұрын

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

  • @johnsonturing6423

    @johnsonturing6423

    10 жыл бұрын

    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.

  • @stephenkamenar

    @stephenkamenar

    10 жыл бұрын

    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

  • @johnsonturing6423

    @johnsonturing6423

    10 жыл бұрын

    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.

  • @marcoscataglini8023

    @marcoscataglini8023

    10 жыл бұрын

    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.

  • @Kalumbatsch

    @Kalumbatsch

    8 жыл бұрын

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

  • @deemon710
    @deemon71010 ай бұрын

    Has anyone solved the $30k problem?

  • @rdormer
    @rdormer10 жыл бұрын

    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?

  • @gdogvibes1
    @gdogvibes111 жыл бұрын

    Yea.. I need to practice my math:(

  • @6417893265q784256128
    @6417893265q78425612811 жыл бұрын

    I can demonstrate NP = PM ( Perpetuom Mobile ) .

  • @faceshed
    @faceshed10 жыл бұрын

    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?

  • @jidma

    @jidma

    10 жыл бұрын

    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.

  • @faceshed

    @faceshed

    10 жыл бұрын

    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.

  • @mitchumsport
    @mitchumsport10 жыл бұрын

    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.

  • @danmclittle236

    @danmclittle236

    8 жыл бұрын

    +mitchumsport hey mitch, can you tell me how I would make money if I figured out how to factor numbers?

  • @mitchumsport

    @mitchumsport

    8 жыл бұрын

    +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

  • @danmclittle236

    @danmclittle236

    8 жыл бұрын

    +mitchumsport how would you do that?

  • @danmclittle236

    @danmclittle236

    8 жыл бұрын

    +Dan McLittle I mean, If you had a way to get the prime factorization, how would you get the information from users.

  • @daddust

    @daddust

    3 жыл бұрын

    All the bitcoin would be mine just before NSA commandos took me to the Antartic bunker.

  • @myempathy1
    @myempathy19 жыл бұрын

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

  • @budabudimir1
    @budabudimir111 жыл бұрын

    Perelman refused 1M $ :)

  • @Going2MakeItSo
    @Going2MakeItSo9 жыл бұрын

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

  • @nullvoid12
    @nullvoid128 ай бұрын

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

  • @glindin
    @glindin10 жыл бұрын

    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.

  • @glindin

    @glindin

    10 жыл бұрын

    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! ;)

  • @HeyItzMeDawg

    @HeyItzMeDawg

    9 жыл бұрын

    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.

  • @Roberts536
    @Roberts53611 жыл бұрын

    great talk. the host looks like boris johnson

  • @justadrummervienna
    @justadrummervienna11 жыл бұрын

    my answer is: yes you must search!

  • @chris77jay77
    @chris77jay7711 жыл бұрын

    I came here to brush up on my elementary mathematics.

  • @aq1q
    @aq1q11 жыл бұрын

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

  • @Hanible
    @Hanible5 жыл бұрын

    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.

  • @Highencast
    @Highencast11 жыл бұрын

    ummmmmm umm um "silence*

  • @Muzikrazy213
    @Muzikrazy21311 жыл бұрын

    And God only knows how much money the attendees paid.

  • @andenandenia
    @andenandenia11 жыл бұрын

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

  • @citamorc
    @citamorc11 жыл бұрын

    Oh yeah? What if p is zero, huh?

  • @tiziano88
    @tiziano8811 жыл бұрын

    COMIC SAAAAAAAAAANS

  • @alexdroman
    @alexdroman10 жыл бұрын

    Anyone else here from Elementary?

  • @Wyeez
    @Wyeez11 жыл бұрын

    WHY COMIC SANS, WHY? :l

  • @607

    @607

    3 жыл бұрын

    One of the RSA presentations also uses Comic Sans. :)

  • @RogerKeulen
    @RogerKeulen11 жыл бұрын

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

  • @doceigen
    @doceigen11 жыл бұрын

    And 'personal problems are evil'? What a way to disrespect someone's opinion, post modern dude.

  • @OLExGREG
    @OLExGREG11 жыл бұрын

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

  • @DrunkenNINJA1998
    @DrunkenNINJA199810 жыл бұрын

    the answer is 2

  • @perseapina

    @perseapina

    5 жыл бұрын

    42