Are there any problems that are solvable in polynomial time only if P!=NP, and otherwise solvable in (say) $O(2^n)$ time?

A simple example would be: If P!=NP, compute a primality test for a random n-bit number, otherwise, evaluate a random worst-case position in generalized chess of a nxn board with 2n pieces on each side. That seems kinda hacky though. Are there any more natural examples?

  • 1
    $\begingroup$ Not exactly what you're asking about, but there are connections between circuit lower bounds (e.g. SAT requires super-polynomial size circuits, implying particularly that P != NP) and derandomization (e.g. BPP = P, in particular some new problems would be known to be in P). But I'm pretty sure that P!=NP is not a strong enough assumption for any such result. $\endgroup$
    – usul
    Commented Sep 9, 2014 at 3:54
  • 8
    $\begingroup$ If $P\neq NP$ is provable in ZFC (open problem) then an algorithm could be: on input $x$, if $x$ doesn't encode a valid proof of $P\neq NP$ then ouput $0$ otherwise simulate the Turing machine $x$ on empty tape for $2^{|x|}$ steps and output $0$ if it rejects or doesn't halt, $1$ otherwise. $\endgroup$ Commented Sep 9, 2014 at 7:11
  • $\begingroup$ How about if it is provable in HoTT but not ZFC? $\endgroup$ Commented Sep 9, 2014 at 11:49
  • $\begingroup$ @MarzioDeBiasi That's true, thanks, and really as Chad pointed out you could use any set of axioms in place of ZFC, hopefully using a consistent one that can prove in a meaningful way that P!=NP. That still feels pretty hacky though, I mean like my example we could easily replace the $2^[|x|]$ with any other desired time complexity (including, say, solving the halting problem). $\endgroup$
    – Phylliida
    Commented Sep 9, 2014 at 19:52
  • $\begingroup$ It's possible there are no natural looking examples of the type I'm asking for, but it seems like formal definitions of "natural" (say, high probability of picking this problem given a random problem in all problems in EXP) sorta lose out on some of the meaning so it might not be that meaningful to try and prove that, I'm not sure. $\endgroup$
    – Phylliida
    Commented Sep 9, 2014 at 19:53

1 Answer 1


If we knew a specific computable language $L$ such that we could prove $L\in\mathrm P\iff\mathrm P\ne\mathrm{NP}$, this would make $\mathrm P\ne\mathrm{NP}$ equivalent to a $\Sigma^0_2$ sentence. While $\mathrm P\ne\mathrm{NP}$ is $\Pi^0_2$, it is not known to be $\Sigma^0_2$, and this is outright false in the relativized world (see https://cstheory.stackexchange.com/a/16644).


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.