4 ms·

#8 is a fun one (some of these answers are half-joking): "Proof by contradiction. Assume P = NP. Let y be a proof that P = NP. The proof y can be verified in p

#8 is a fun one (some of these answers are half-joking): "Proof by contradiction. Assume P = NP. Let y be a proof that P = NP. The proof y can be verified in polynomial time by a competent computer scientist, the existence of which we assert. However, since P = NP, the proof y can be generated in polynomial time by such computer scientists. Since this generation has not yet occurred (despite attempts by such computer scientists to produce a proof), we have a contradiction."

surrey-fringe 10y ago
Is that true -- that the proof (if we produce one) will be verifiable in polynomial time?
- petters 10y ago
  It is not really meaningful to talk about a single instance being verifiable in polynomial time.
  - surrey-fringe 10y ago
    Well I was open to evidence that applies generally, but sure.
- elehack 10y ago
  Technically, yes, but practically, no. THEOREMS (the language of correct proofs) is in P; given a correct proof (possibly restricted to being in first-order logic), it can be verified in polynomial time. In the first-order logic case, all you have to do is read the proof from beginning to end and verify that each statement follows from either an axiom or an already-established statement. This is done entirely syntactically, requiring no knowledge of the underlying mathematics. However, to do this requires formalizing the entire proof in machine-checkable format, which is a substantial undertaking even for relatively simple proofs and will likely take far longer than polynomial time.
- paulddraper 10y ago
  As petters points out, "X time" has no useful meaning here. An interesting and still valid point, however, is that P=NP may be undecidable (in the sense of Gödel's incompleteness theorem). In other words, our current axioms may be insufficient to prove or disprove P=NP. http://www.scottaaronson.com/papers/pnp.pdf http://www.scottaaronson.com/papers/pnp.pdf > P != NP is either true or false. It’s one or the other. But we may not be able to prove which way it goes, and we may not be able to prove that we can’t prove it.

surrey-fringe 10y ago

Is that true -- that the proof (if we produce one) will be verifiable in polynomial time?

petters 10y ago
It is not really meaningful to talk about a single instance being verifiable in polynomial time.
- surrey-fringe 10y ago
  Well I was open to evidence that applies generally, but sure.
elehack 10y ago
Technically, yes, but practically, no. THEOREMS (the language of correct proofs) is in P; given a correct proof (possibly restricted to being in first-order logic), it can be verified in polynomial time. In the first-order logic case, all you have to do is read the proof from beginning to end and verify that each statement follows from either an axiom or an already-established statement. This is done entirely syntactically, requiring no knowledge of the underlying mathematics. However, to do this requires formalizing the entire proof in machine-checkable format, which is a substantial undertaking even for relatively simple proofs and will likely take far longer than polynomial time.
paulddraper 10y ago
As petters points out, "X time" has no useful meaning here. An interesting and still valid point, however, is that P=NP may be undecidable (in the sense of Gödel's incompleteness theorem). In other words, our current axioms may be insufficient to prove or disprove P=NP. http://www.scottaaronson.com/papers/pnp.pdf http://www.scottaaronson.com/papers/pnp.pdf > P != NP is either true or false. It’s one or the other. But we may not be able to prove which way it goes, and we may not be able to prove that we can’t prove it.