10
$\begingroup$

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?

$\endgroup$
  • 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 Sep 9 '14 at 3:54
  • 7
    $\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$ – Marzio De Biasi Sep 9 '14 at 7:11
  • $\begingroup$ How about if it is provable in HoTT but not ZFC? $\endgroup$ – Chad Brewbaker Sep 9 '14 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 Sep 9 '14 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 Sep 9 '14 at 19:53
14
$\begingroup$

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).

$\endgroup$

Your Answer

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

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