We know we have a long way to go before we come to a proof of P $\neq$ NP. We also know that this road is studded with minor conjectures that will have to be proved/disproved in order to arrive at the much sought-after truth.

My question is the following: if tomorrow a proof of P $\neq$ NP would appear, what would be all the CS open problems that such a proof would solve?

  • $\begingroup$ Many results in complexity theory are conditional on P≠NP. $\endgroup$ – Yuval Filmus Nov 7 at 12:31
  • $\begingroup$ For results and conjectures that are weaker than P≠NP, and are suspected to be on the road to prove P≠NP, see Section 6 in Scott Aaronson's P vs NP survey scottaaronson.com/papers/pnp.pdf. $\endgroup$ – Laakeri Nov 8 at 14:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.