4 ms·
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
by 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 agoYes, 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