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

<p>Suppose we take a NEXP-complete language with input <span class="math-container">$x$</span> in binary and witness <span class="math-container">$y\in\{0,1\}^{2^{poly(|x|)}}$</span> such that the verifying TM runs for time <span class="math-container">$2^{poly(|x|)}$</span> on input <span class="math-container">$(x,y)$</span>. </p>

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

<p>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 <span class="math-container">$y$</span> be specified in unary too?</p>

CC BY-SA 4.0
2019-03-10T14:46:25.983Z
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.
chazisop
CC BY-SA 4.0
2019-03-10T21:26:50.690Z
Is there a useful concept of an exptime reduction (as opposed to a polytime/Turing reduction) for unary problems, or indeed for problems generally?
Hans Schmuber
CC BY-SA 4.0
2019-03-11T02:25:56.533Z
Also, FYI, the relation in fact goes both ways. The [Hartmanis-Immerman-Sewelson Theorem](https://doi.org/10.1016/S0019-9958(85)80004-8) says that there exists a sparse set in NP - P iff NEXP neq EXP.
Joshua Grochow
CC BY-SA 4.0
2019-03-11T17:16:56.737Z
One final question: the above presumably rules out any unary language being NEXP-complete too?
Hans Schmuber
<cc.complexity-theory><np-hardness><unary-languages>
Take a NEXP-complete problem and then have the input in unary. Why is this not NP-complete?
Hans Schmuber
# Take a NEXP-complete problem and then have the input in unary. Why is this not NP-complete?

(Asked by: username_0 on 2019-03-10)

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?

**Tags:** cc.complexity-theory, np-hardness, unary-languages

> **Comments:**
> **username_1**: 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.  
> **username_0**: Is there a useful concept of an exptime reduction (as opposed to a polytime/Turing reduction) for unary problems, or indeed for problems generally?  
> **username_2**: Also, FYI, the relation in fact goes both ways. The [Hartmanis-Immerman-Sewelson Theorem](https://doi.org/10.1016/S0019-9958(85)80004-8) says that there exists a sparse set in NP - P iff NEXP neq EXP.  
> **username_0**: One final question: the above presumably rules out any unary language being NEXP-complete too?  

---

## 0 answers

