9 ms·
My survey article on P vs. NP (2017)
- d3ckard 6y agoThis is IMO, by far, the most important problem of computer science. I often wonder whether I will live long enough to see it settled one way or the other. In any case, definitely recommended reading.
- zeroonetwothree 6y agoI wouldn’t count on it.
- anamexis 6y agoWould proving P != NP have any interesting implications? I know P = NP would, but was just curious if P != NP would mean anything other than "well, now we know we can't do it in polynomial time."
- __s 6y agoNot too much, especially since for the most part the world has gone ahead betting on P!=NP But the techniques used would likely be insightful. Particularly with proving cryptographic protocols beyond "we had a contest & damn are these bits ever uncorrelated"
- zests 6y agoEven proving P=NP would not necessarily have any practical applications. Practicality is typically not a concern in complexity theory. Even some problems that have been shown to be in P are still usually solved with non-polynomial algorithms (Linear Programming).
- daxfohl 6y agoYeah there is no guarantee any proof would even show you how to create a polynomial algorithm for some NP problem. It could just show some logical contradiction that happens if P=NP is false. Or obviously even if the proof does show you how to do it but the exponent is some insanely large number (see some of Scott Aaronson's other articles about "busy beaver numbers"), then that does not change anything practically either.
- PartiallyTyped 6y agoI disagree. If P=NP, then we could very well start searching the space of polynomial algorithms until we find something that works and discard anything that is not polynomial - which we can check apriori since the halting problem assumes we can't peak into the Turing machine, when in practice, we can.
- zests 6y agoEven knowing a polynomial algorithm for SAT would not have practical implications unless the algorithm has a reasonable run time. Matrix multiplication is a great example of a problem where the best known runtime complexity algorithms are not used even though for matrixes the size of the universe they would be faster.
- PartiallyTyped 6y agoI don't disagree, but it may also help in getting tighter bounds on algorithms, iirc Matrix Maltiplication doesn't have a tight Omega function. Also, finding such algorithms should significantly expand our capabilities by expanding our understanding.
- kongolongo 6y agoCouldn't we assume P=NP and try this anyways?
- PartiallyTyped 6y agoI mean, you could do that, but knowing it exists makes the search worthwhile.
- jcranmer 6y agoWhen most people are taught algorithms, it's done so in a way that seems to emphasize that algorithms in "P" are very fast--I doubt many people have encountered an algorithm worse than O(n^3) that's still polynomial--and the "NP" algorithms are very slow, and this gives strong rise to a solution in "P" must necessarily be better than one that is "NP". Even when complexity classes are introduced, and there's a segment on "you know, you're ignoring constant factors which could be really big," there's still no practical experience with cases that do have big constant factors. Let me give an example where such a case exists. In 2005, a paper came out finding an algorithm for determining undirected graph connectivity in log space, which means you can't keep an unbounded stack of nodes that you have visited (as the trivial depth-first or breadth-first search algorithms do). This algorithm relies on converting the input graph using an "expander graph," basically replacing every node with an instance of a graph. When I computed how large an expander graph had to be, I found that the smallest one was ... 3^65536. It's still a constant factor, but it's larger than the number of atoms in the universe. This kind of constant factor isn't unusual for combinatorics problems (this is the same kind of space where Graham's number comes up). My suspicion is that if P=NP, it's likely to be so only via this kind of crazy combinatorial input, which is to say, the P algorithm is completely impractical. Outside of combinatorial algorithms, there are several other cases where the asymptotically faster algorithms are generally disfavored due to practical concerns: primality testing (AKP is a P algorithm, but slower in practice); matrix multiplication (we keep finding better exponents, but the dominant algorithm remains Strassen, and even then, that's only going to be used for distributed matrix multiplication). You mention linear programming, but my understanding is that interior point methods are generally preferred in modern implementations over simplex methods, the former being polynomial and the latter exponential (although very often polynomial in practice--another great example of typical case being far faster than worst case).
- pretty_bubbles 6y agoThe proof is likely to turn up some interesting factors. The reason why something is P and something else is NP is the big question.
- vinceguidry 6y agoThe proof itself would be super-interesting, pointing to lots of new areas of mathematical inquiry. It's a bit like the old logic problem of not being able to prove something doesn't exist, in order to be able to do so, you need to look literally everywhere and show that it's not there. A proof of P!=NP would tell us two things. First, that there's something inherently different about NP-complete problems, and the proof would tell us exactly what. Second, it would tell us how to figure that out, inevitably with an entirely new toolset for classifying problems. It would reverberate all over the computational complexity space and probably even give us new ideas for number theory.
- tgflynn 6y ago> First, that there's something inherently different about NP-complete problems, and the proof would tell us exactly what. The way I see it NP problems require exponential time by default. The reason some of them can be solved in polynomial time is because those problems contain some special structure that allows you to short-circuit the general solution with some kind of "trick". Then P vs. NP boils down to does there exist a "general trick". In other words do all NP problems contain structure that can be exploited to short-circuit the calculation or not. I do agree that actually proving that P != NP seems like it would require discovering some as yet unknown structure behind virtually all of mathematics, simply because the hypothetical "general trick" could be hidden in just about any mathematical structure we know about (or even in one we haven't discovered yet).
- teraflop 6y ago> In other words do all NP problems contain structure that can be exploited to short-circuit the calculation or not. And we can strengthen this statement a bit, to really hammer home the intuition of why P=NP would be such a radical discovery. "Simulating an arbitrary non-deterministic Turing machine for K steps" is itself an NP-complete problem, which would be solvable by a polynomial algorithm if P=NP. In other words, it's not just that all NP problems would have some structure that a sufficiently clever programmer could exploit; it's that there would exist a single algorithm that could automatically discover and exploit such structure in any NP problem.
- SilasX 6y agoI think Aaronson addresses that in 1.2.6 as the "obviousness objection", "a proof of P ̸= NP—confirming that indeed, we can’t do something that no reasonable person would ever have imagined we could do—gives almost no useful information." To which he replies, >>to make a sweeping statement like P ̸= NP, about what polynomial-time algorithms can't do, will require an unprecedented understanding of what they can do. This will almost certainly entail the discovery of many new polynomial-time algorithms, some of which could have practical relevance. In Section 6, we’ll see much more subtle examples of the “duality” between algorithms and impossibility proofs, with progress on each informing the other.
- hannob 6y agoSo there's a problem we have with today's cryptography that we basically have to hope it's secure, but we can't proove it. It's basically "enough people looked at it, noone found a way to break it, it should be okay". That's what we have, but it's not really comforting. Now if you think what it'd mean to proove that e.g. a public key crypto system is secure, it almost implies that you'd need to proove p!=np before that. I.e. prooving p!=np would not proove that cryptography is secure, but it may be the first step and the understanding gained from prooving p!=np may mean that there's a much better understanding of complexity in general, which will help.
- fooker 6y agoWhat has cryptography got to do with p!=np ?
- macmmajor 6y agoIf p == np, then interger factorization can be reduced to k-sat, which is solvable in p time https://cs.stackexchange.com/questions/6650/how-can-p-np-enhance-integer-factorization https://cs.stackexchange.com/questions/6650/how-can-p-np-enh...
- fooker 6y agoNeat, thanks!
- raverbashing 6y ago> then integer factorization can be reduced to k-sat, It can be reduced already, but then 3-sat can be solved in P time
- js8 6y agoIf P=NP, then you can invert in polynomial time (assuming this is practical) arbitrary boolean functions and thus solve any equations (that can be specified as a boolean circuit), find keys to any cryptosystem etc. For example, you can assume part of the plaintext (like a header in transmission) and solve an equation (which can be restated as a SAT instance) that yields you a key assuming certain cryptographic algorithm was used. So pretty much all cryptography relies on P!=NP.
- OscarCunningham 6y agoIt might be useful for proving that cryptographic protocols are guaranteed secure (i.e. that cracking them is not in P). I don't know if there are any existing protocols known to be in NP (e.g. factoring for RSA is not known to be NP hard) but it would be huge progress in that direction.
- d3ckard 6y agoIt would let us understand way better what computation really is I think. If we can separate computational problem into classes, it means we can create some hierarchy of computations and understand what makes them move between those classes. It might be much more enlightening than all the crazy stuff that could happen if P=NP.
- j-pb 6y agoYES! If P != NP then there is an infinity hierarchy of problems between them which are themselves complete in terms of difficulty within their level. https://en.wikipedia.org/wiki/NP-intermediate https://en.wikipedia.org/wiki/NP-intermediate Under the assumption that we understand P and NP a heck of a lot more if we were able to proof their distinctness, this hierarchy could possibly be used for actually USEFUL proof of work in crypto currencies, by choosing problems with exactly the right difficulty from a problem domain like protein folding.
- matsemann 6y agoSomething not loading right? https://i.imgur.com/Z8jwPHc.png https://i.imgur.com/Z8jwPHc.png Archive: http://web.archive.org/web/20210323141221/https://www.scottaaronson.com/blog/?p=3095 http://web.archive.org/web/20210323141221/https://www.scotta... Archive of the pdf in question: http://web.archive.org/web/20210313130122/https://www.scottaaronson.com/papers/pnp.pdf http://web.archive.org/web/20210313130122/https://www.scotta...
- deleted 6y ago[deleted]
- adamnemecek 6y agoI think that P==NP, just not on Turing machines. A prism calculates Fourier in “O(1)” which can be used to factorize in “O(1)” and thereby solve NP in P.
- WJW 6y agoIf you want to think of prisms as calculating devices, isn't a prism technically a massively parallel device where all the molecules are a "core" of sorts? It still does at least O(N log N) work I think, it just all happens in parallel. You can also find the minimum element of a list in logarithmic time instead of linear time if you have enough parallelism available, even though finding the minimum element is O(N).
- bidirectional 6y agoWhat model of computation then? If you abandon Turing machines with their infinite memory, aren't you just in the land of lookup tables? I can model a prism and all possible ways light can hit it as a (intractably huge) dictionary, everything is O(1).
- adamnemecek 6y agoYou really aren’t in the land of lookup tables no.
- bidirectional 6y agoWhy not? I realise there are non-Turing complete models of computation that cannot be described by a lookup table (e.g. coinduction), but are they physically realisable?
- adamnemecek 6y agoAnyone who says anything besides “I don’t know” is lying.
- enkid 6y agoDoes a prism truly solve a Fourier in "O(1)" or is it so fast it seems to be "O(1)"?
- Sebb767 6y agoTitle needs a (2017), I think
- IndySun 6y agoFor your next free 45 mins... Melvyn Bragg and guests discuss the problem of P versus NP, which has a bearing on online security. There is a $1,000,000 prize on offer from the Clay Mathematical Institute for the first person to come up with a complete solution. At its heart is the question "are there problems for which the answers can be checked by computers, but not found in a reasonable time?" If the answer to that is yes, then P does not equal NP. However, if all answers can be found easily as well as checked, if only we knew how, then P equals NP. The area has intrigued mathematicians and computer scientists since Alan Turing, in 1936, found that it's impossible to decide in general whether an algorithm will run forever on some problems. Resting on P versus NP is the security of all online transactions which are currently encrypted: if it transpires that P=NP, if answers could be found as easily as checked, computers could crack passwords in moments. With Colva Roney-Dougal Reader in Pure Mathematics at the University of St Andrews Timothy Gowers Royal Society Research Professor in Mathematics at the University of Cambridge And Leslie Ann Goldberg Professor of Computer Science and Fellow of St Edmund Hall, University of Oxford https://www.bbc.co.uk/programmes/b06mtms8 https://www.bbc.co.uk/programmes/b06mtms8
- krnsll 6y agoGreat recommendation. When I first listened to this podcast, I was impressed by how the conversation managed to hit the sweet spot of engagement for both non technical (a friend I shared it with) and technical/mathematical (myself) audiences. Later learned that Melvyn Bragg hosted two of guests here (Gowers and Roney-Dougal) for another good conversation on the notions of randomness and pseudo-randomness. https://www.bbc.co.uk/programmes/b00x9xjb https://www.bbc.co.uk/programmes/b00x9xjb
- jfengel 6y agoThe show is remarkable for the breadth it covers. It brings in four academics -- scholars, not popularizers -- on anything from art, philosophy, history, culture, etc. Other recent topics are David Ricardo and The Bacchae. And every week, Bragg intelligently moderates the conversation -- not as an expert, but as somebody who sounds like he's better informed than just feeding them the outlines they write for him.