5 ms·

This 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 a

This 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 ago
I wouldn’t count on it.
anamexis 6y ago
Would 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 ago
  Not 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 ago
  Even 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 ago
    Yeah 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 ago
    I 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 ago
      Even 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 ago
        I 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 ago
      Couldn't we assume P=NP and try this anyways?
      - PartiallyTyped 6y ago
        I mean, you could do that, but knowing it exists makes the search worthwhile.
  - jcranmer 6y ago
    When 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 ago
  The 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 ago
  The 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 ago
  I 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 ago
  So 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 ago
    What has cryptography got to do with p!=np ?
    - macmmajor 6y ago
      If 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 ago
        Neat, 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 ago
      If 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 ago
  It 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 ago
  It 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 ago
  YES! 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.

zeroonetwothree 6y ago

I wouldn’t count on it.

anamexis 6y ago

Would 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 ago
Not 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 ago
Even 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 ago
  Yeah 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 ago
  I 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 ago
    Even 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 ago
      I 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 ago
    Couldn't we assume P=NP and try this anyways?
    - PartiallyTyped 6y ago
      I mean, you could do that, but knowing it exists makes the search worthwhile.
- jcranmer 6y ago
  When 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 ago
The 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 ago
The 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 ago
I 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 ago
So 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 ago
  What has cryptography got to do with p!=np ?
  - macmmajor 6y ago
    If 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 ago
      Neat, 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 ago
    If 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 ago
It 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 ago
It 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 ago
YES! 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.