3 ms·

Is it possible that there's something about the nature of computation that makes it so that P = NP / P != NP is simply unprovable/unknowable?

bawolff 3y ago
Yes its possible p vs np is actually undecidable
- sterlind 3y ago
  if P=NP, could the question still be undecidable? as in, could there be an algorithm for 3SAT that, in practice, happens to be polynomial-time and correct, but there's no way to prove the algorithm's correctness and/or time complexity under any system of formal logic?
  - dmurray 3y ago
    Yes, it seems that the state of the art admits this as a possibility (though it seems surprising, and you can make a hand wavy argument dismissing it, as another poster does downthread). Eg this survey by Scott Aaronson: https://www.scottaaronson.com/papers/pnp.pdf#page=26 https://www.scottaaronson.com/papers/pnp.pdf#page=26
YetAnotherNick 3y ago
It's not impossible to prove P==NP if that is the case as the program is the proof. Also if we assume "if P==NP then there exists program less than a trillion lines" then P!=NP is provable if that is the case.
- joe_the_user 3y ago
  Exhibiting program that terminates in polynomial time for NP problem isn't sufficient to prove P==NP. You also need to actually prove the function terminates in polynomial time. And I could easily imagine that the general problem "does program P(X) terminate in time less than f(X)" is equivalent to the halting problem but in any case it's not at all guaranteed you could create such a proof.
- sterlind 3y ago
  the program isn't the proof. you have to prove that the program always gives the correct answer, and works inside some time bound. what if, say, it generates the Collatz sequence as a subroutine? good luck proving that the program is polynomial when we can't even prove that sequence always converges.
deleted 3y ago
[deleted]
tsimionescu 3y ago
I don't think we know enough about how computation relates to proof fidning to be able to say. While (sufficiently well specified) proof verification is pretty clearly a computation, creating a new proof is less clear. Given that the space of possible proofs is infinite, I don't think a brute force approach is possible even for a nondeterministic algorithm, so I don't think that, even if P=NP were the truth we would have a clear reason to expect to find a proof of this.

bawolff 3y ago

Yes its possible p vs np is actually undecidable

sterlind 3y ago
if P=NP, could the question still be undecidable? as in, could there be an algorithm for 3SAT that, in practice, happens to be polynomial-time and correct, but there's no way to prove the algorithm's correctness and/or time complexity under any system of formal logic?
- dmurray 3y ago
  Yes, it seems that the state of the art admits this as a possibility (though it seems surprising, and you can make a hand wavy argument dismissing it, as another poster does downthread). Eg this survey by Scott Aaronson: https://www.scottaaronson.com/papers/pnp.pdf#page=26 https://www.scottaaronson.com/papers/pnp.pdf#page=26

YetAnotherNick 3y ago

It's not impossible to prove P==NP if that is the case as the program is the proof. Also if we assume "if P==NP then there exists program less than a trillion lines" then P!=NP is provable if that is the case.

joe_the_user 3y ago
Exhibiting program that terminates in polynomial time for NP problem isn't sufficient to prove P==NP. You also need to actually prove the function terminates in polynomial time. And I could easily imagine that the general problem "does program P(X) terminate in time less than f(X)" is equivalent to the halting problem but in any case it's not at all guaranteed you could create such a proof.
sterlind 3y ago
the program isn't the proof. you have to prove that the program always gives the correct answer, and works inside some time bound. what if, say, it generates the Collatz sequence as a subroutine? good luck proving that the program is polynomial when we can't even prove that sequence always converges.

deleted 3y ago

[deleted]

tsimionescu 3y ago

I don't think we know enough about how computation relates to proof fidning to be able to say. While (sufficiently well specified) proof verification is pretty clearly a computation, creating a new proof is less clear. Given that the space of possible proofs is infinite, I don't think a brute force approach is possible even for a nondeterministic algorithm, so I don't think that, even if P=NP were the truth we would have a clear reason to expect to find a proof of this.