It is known that if any unary language is NP-complete, then P=NP.

Suppose we take a NEXP-complete language with input $x$ in binary and witness $y\in\{0,1\}^{2^{poly(|x|)}}$ such that the verifying TM runs for time $2^{poly(|x|)}$ on input $(x,y)$.

Now change the problem such that $x$ is specified in unary. Let $|x|_u$ be the unary length. Now $y\in\{0,1 \}^{poly(|x|_u)}$. The verifying TM then runs for time $poly(|x|_u)$ and will deterministically output whether $y$ is a valid witness.

It seems like since the original problem was NEXP-complete, the unary version of the problem should be NP-complete. However, surely this would then imply P=NP. What am I missing? Should the witness $y$ be specified in unary too?

  • 6
    $\begingroup$ The reductions f used to reduce any $L \in NEXP$ to your NEXP-complete problem , say $B$ needed polytime and they output f(x) in binary. But now they must convert their output f(x) to unary, which they cannot do in polytime. Thus you have shown your problem to be in NP but not complete. $\endgroup$ – chazisop Mar 10 '19 at 14:46
  • $\begingroup$ Is there a useful concept of an exptime reduction (as opposed to a polytime/Turing reduction) for unary problems, or indeed for problems generally? $\endgroup$ – user138901 Mar 10 '19 at 21:26
  • 3
    $\begingroup$ Also, FYI, the relation in fact goes both ways. The Hartmanis-Immerman-Sewelson Theorem says that there exists a sparse set in NP - P iff NEXP neq EXP. $\endgroup$ – Joshua Grochow Mar 11 '19 at 2:25
  • $\begingroup$ One final question: the above presumably rules out any unary language being NEXP-complete too? $\endgroup$ – user138901 Mar 11 '19 at 17:16

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.