4 ms·

I hear this statement frequently when P = NP is discussed, but as someone not involved in computer science I have a hard time understanding it. Could you expla

I hear this statement frequently when P = NP is discussed, but as someone not involved in computer science I have a hard time understanding it. Could you explain what some of those consequences be? Does P = NP really need to be proved to achieve those practical consequences? Can't it just be assumed to be true and then see what the result is?

ramidarigaz 16y ago
If P = NP were proved to be true, it would tell us that there are solutions to a certain class of problems. Assuming it's true doesn't give us those solutions. Wikipedia should answer most of your questions regarding the consequences: http://en.wikipedia.org/wiki/P_%3D_NP#Consequences_of_proof http://en.wikipedia.org/wiki/P_%3D_NP#Consequences_of_proof
- nkassis 16y ago
  To be a little more precise, proving P=NP would mean that there are algorithms to solve those problems that take polynomial time (can be calculated with a polynomial). NP problems can be solved, it's just slow (think brute force method, running through all the possibilities).
- jules 16y ago
  Not true. A polynomial time algorithm for NP complete programs is known (if P=NP that is). You just need to prove P=NP to prove that it is polynomial time. http://en.wikipedia.org/wiki/P_versus_NP_problem#Polynomial-time_algorithms http://en.wikipedia.org/wiki/P_versus_NP_problem#Polynomial-...
lulin 16y ago
If I remember correctly, any proof of P = NP would be have to be constructive, so it would immediately give us a fast algorithm for ALL NP-complete problems, as they can all be reduced to each other.
- faboo 16y ago
  It isn't actually _necessary_ for a P=NP proof to be constructive. A constructive proof would probably be easier to reason through, but it is prossible to prove the existence of an algorithm without providing one.
- btilly 16y ago
  Not so. Pure existence proofs can be non-constructive. The first historical example of an important proof which was non-constructive was Hilbert's Basis Theorem in 1888, which solved a famous problem posed by Paul Gordon. It is now viewed as in some sense being the first salvo in the debate over constructivism in the 20th century. See http://en.wikipedia.org/wiki/David_Hilbert#The_finiteness_theorem http://en.wikipedia.org/wiki/David_Hilbert#The_finiteness_th... for more.
abstractbill 16y ago
Intuitively: NP questions take a long time to answer. P questions take much less time. The statement "P = NP" means that any NP question can be transformed into a P question. Answering the P question gives you an answer to the NP question. So, if P = NP, then we can answer questions that we thought were slow, much more quickly than we would have thought possible. Proving P = NP would (presumably) give you that method for transforming NP problems into P problems. So you would suddenly be able to figure things out easily that currently are hard and take a lot of computing power. It's often assumed that P = NP would make cryptographic problems much easier to break, but apparently that's not really the case: http://world.std.com/~reinhold/p=np.txt http://world.std.com/~reinhold/p=np.txt
- miloshh 16y ago
  Yeah, the common complaint against "P=NP would break cryptography" is "but what if the polynomial algorithm for (say) SAT is n^10000?". That is not very likely, in my opinion. Even though "polynomial" is not equivalent to "efficient", in practice all problems that have a polynomial algorithm also have an efficient algorithm.
  - dfox 16y ago
    There are many problems that have polynomial algorithm, that is not especially fast for practical problems (matrix multiplication comes to mind for example, for which there isn't even any proof that fastest known algorithm is in fact optimal)
    - miloshh 16y ago
      That's not a very good example - square matrix multiplication is O(n^1.5) (where n is the input size) and extremely fast in practice. (Though, as you say, there could still be an O(n) algorithm - this is not known). What I said is true even for linear programming (a P-complete problem) - it has polynomial and efficient algorithms - though the latter are actually not polynomial in the worst case. :)
      - 16y ago

ramidarigaz 16y ago

If P = NP were proved to be true, it would tell us that there are solutions to a certain class of problems. Assuming it's true doesn't give us those solutions. Wikipedia should answer most of your questions regarding the consequences: http://en.wikipedia.org/wiki/P_%3D_NP#Consequences_of_proof http://en.wikipedia.org/wiki/P_%3D_NP#Consequences_of_proof

nkassis 16y ago
To be a little more precise, proving P=NP would mean that there are algorithms to solve those problems that take polynomial time (can be calculated with a polynomial). NP problems can be solved, it's just slow (think brute force method, running through all the possibilities).
jules 16y ago
Not true. A polynomial time algorithm for NP complete programs is known (if P=NP that is). You just need to prove P=NP to prove that it is polynomial time. http://en.wikipedia.org/wiki/P_versus_NP_problem#Polynomial-time_algorithms http://en.wikipedia.org/wiki/P_versus_NP_problem#Polynomial-...

lulin 16y ago

If I remember correctly, any proof of P = NP would be have to be constructive, so it would immediately give us a fast algorithm for ALL NP-complete problems, as they can all be reduced to each other.

faboo 16y ago
It isn't actually _necessary_ for a P=NP proof to be constructive. A constructive proof would probably be easier to reason through, but it is prossible to prove the existence of an algorithm without providing one.
btilly 16y ago
Not so. Pure existence proofs can be non-constructive. The first historical example of an important proof which was non-constructive was Hilbert's Basis Theorem in 1888, which solved a famous problem posed by Paul Gordon. It is now viewed as in some sense being the first salvo in the debate over constructivism in the 20th century. See http://en.wikipedia.org/wiki/David_Hilbert#The_finiteness_theorem http://en.wikipedia.org/wiki/David_Hilbert#The_finiteness_th... for more.

abstractbill 16y ago

Intuitively: NP questions take a long time to answer. P questions take much less time. The statement "P = NP" means that any NP question can be transformed into a P question. Answering the P question gives you an answer to the NP question. So, if P = NP, then we can answer questions that we thought were slow, much more quickly than we would have thought possible. Proving P = NP would (presumably) give you that method for transforming NP problems into P problems. So you would suddenly be able to figure things out easily that currently are hard and take a lot of computing power. It's often assumed that P = NP would make cryptographic problems much easier to break, but apparently that's not really the case: http://world.std.com/~reinhold/p=np.txt http://world.std.com/~reinhold/p=np.txt

miloshh 16y ago
Yeah, the common complaint against "P=NP would break cryptography" is "but what if the polynomial algorithm for (say) SAT is n^10000?". That is not very likely, in my opinion. Even though "polynomial" is not equivalent to "efficient", in practice all problems that have a polynomial algorithm also have an efficient algorithm.
- dfox 16y ago
  There are many problems that have polynomial algorithm, that is not especially fast for practical problems (matrix multiplication comes to mind for example, for which there isn't even any proof that fastest known algorithm is in fact optimal)
  - miloshh 16y ago
    That's not a very good example - square matrix multiplication is O(n^1.5) (where n is the input size) and extremely fast in practice. (Though, as you say, there could still be an O(n) algorithm - this is not known). What I said is true even for linear programming (a P-complete problem) - it has polynomial and efficient algorithms - though the latter are actually not polynomial in the worst case. :)
    - 16y ago