4 ms·
Yes, and yes. P != NP could be independent from Peano Arithmetic (PA) or the Zermelo-Fraenkel set theory with Axiom of Choice (ZFC) models. That is a separate c
by throwawaymath 7y ago
Yes, and yes. P != NP could be independent from Peano Arithmetic (PA) or the Zermelo-Fraenkel set theory with Axiom of Choice (ZFC) models. That is a separate conjecture which is also presently open.
- lidHanteyk 7y agoSurprisingly, this cannot be the case, not without discovering a completely new kind of independence proof. [0] p26 discusses the problem. > At the end of the day, a polynomial-time algorithm for 3-SAT either exists or it doesn't! [0] https://www.scottaaronson.com/papers/pnp.pdf https://www.scottaaronson.com/papers/pnp.pdf