Hacker News Reader

Comment by snek_case | Hacker News Reader

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?

View on HN

Yes its possible p vs np is actually undecidable

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?

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

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.

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.

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.

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.

Reply on news.ycombinator.com