<p>If <span class="math-container">$N$</span> were written in unary, then the language would be a unary language, i.e., a subset of <span class="math-container">$\{0,1\}^*$</span>.   Every unary language is in P/poly.  That's because a P/poly machine is allowed a separate advice string, one per length of the input.  The advice string for length <span class="math-container">$n$</span> could just describe whether the input <span class="math-container">$1^n$</span> should be accepted or not.  Or, to put it another way, P/poly allows you to specify a separate circuit per input length; so you could use the "always output no" circuit for lengths <span class="math-container">$n$</span> such that <span class="math-container">$1^n$</span> is not part of the language, otherwise the "always output yes" circuit.  See <a href="https://en.wikipedia.org/wiki/P/poly" rel="nofollow noreferrer">https://en.wikipedia.org/wiki/P/poly</a>.</p>

CC BY-SA 4.0
2019-03-07T05:20:43.457Z
2019-03-07T05:20:43.457Z
D.W.
<p>It is always difficult to answer the question <em>why did the authors phrase this in such and such a way</em>, so I can only guess. My guess is that they assume certain background knowledge, which I now lay out.</p>

<p>The only input to the problem in the paper is <span class="math-container">$N$</span>, which is given in binary, because, as the authors mention</p>

<blockquote>
  <p>If instead we were given <span class="math-container">$N$</span> in unary, there would only be one instance per problem size</p>
</blockquote>

<p>It seems intuitive that if the problem were given in unary, then the problem would be <span class="math-container">$NP$</span>-Complete instead of <span class="math-container">$NEXP$</span>-Complete. This intuition is wrong, because then there would be a unary <span class="math-container">$NP$</span>-Complete language. A result of Mahany [3] says that if unary <span class="math-container">$NP$</span>-Complete languages exist, then <span class="math-container">$P=NP$</span> [1]. Since the consequence <span class="math-container">$P=NP$</span> is believed unlikely, the unary version of the problem is probably not interesting, because nothing is believed to reduce to it. (In particular, therefore, it is of no use trying to reduce SAT to Unary-TILING)</p>

<p>They mention that</p>

<blockquote>
  <p>there would only be one instance per problem size, and the problem would trivially be in <span class="math-container">$P/poly$</span>.</p>
</blockquote>

<p>They might mention this for the same reason as above, namely, then there would be an <span class="math-container">$NP$</span>-Complete language in <span class="math-container">$P/poly$</span>, and then <span class="math-container">$NP\subset P/poly$</span>, and a result of Karp and Lipton says that it follows that the polynomial hierarchy collapses (to <span class="math-container">$PH=\Sigma_2^P=\Pi_2^P$</span>, and this result has subsequently been improved [3] to <span class="math-container">$NP\subset P/poly\implies PH=S_2^P$</span> and [4] to <span class="math-container">$NP\subset P/poly\implies MA=AM$</span>). Perhaps the authors of your paper make these remarks because they assume that you are familiar with these results. If that was not the case, then you've learned something today! :)</p>

<p>[1] S. R. Mahaney. Sparse complete sets for NP: Solution of a conjecture by Berman and Hartmanis, Journal of Computer and System Sciences 25:130-143, 1982.</p>

<p>[2] R. M. Karp and R. J. Lipton. Turing machines that take advice, Enseign. Math. 28:191-201, 1982.</p>

<p>[3] J.-Y. Cai. S2P is contained in ZPPNP, Proceedings of IEEE FOCS'2001, pp. 620-629, 2001.</p>

<p>[4] V. Arvind, J. Köbler, U. Schöning, and R. Schuler. If NP has polynomial-size circuits, then MA=AM, Theoretical Computer Science 137, 1995.</p>

CC BY-SA 4.0
2019-03-06T22:47:53.753Z
Uh, no, the remark about the unary language being in P/poly does not rely on Karp Lipton or anything sophisticated. EVERY unary language is in P/poly, even uncomputable ones. This is because a unary language has at most one string for every instance size $n$. So, for every $n$, you either need a circuit which always outputs 0, or a circuit that checks that the input is unary, and if it is, outputs 1.
Sasho Nikolov
CC BY-SA 4.0
2019-03-07T07:37:04.720Z
@SashoNikolov The Karp–Lipton argument is not used in the answer to establish that the unary language is in P/poly (this seems to be taken as a given). Rather, it is used to explain *why* the authors mention this fact.
Emil Jeřábek
CC BY-SA 4.0
2019-03-06T19:13:38.737Z
2019-03-06T19:13:38.737Z
Lieuwe Vinkhuijzen
<p>In this paper by Gottesman and Irani: <a href="https://arxiv.org/abs/0905.2419" rel="nofollow noreferrer">https://arxiv.org/abs/0905.2419</a> , they prove NEXP-hardness of tiling an <span class="math-container">$N\times N$</span> grid. They do so by encoding a TM in the tiles making up the grid. However, they mention that the input to the TM they encode in the tiling problem must be an integer <span class="math-container">$N$</span> in binary rather than unary, otherwise each instance will have a different input size and hence the problem would "trivially be in P/poly" rather than NP. Hence instead they must prove the problem is NEXP-complete rather than NP-complete.  </p>

<p>While I understand why the proof with a binary input gives NEXP-completeness, I don't understand why if <span class="math-container">$N$</span> is input in unary then the problem is trivially hard for P/poly? Unfortunately the model of computation they specify is in terms of TMs rather than circuits so it's not clear to me how this relates to non-uniform circuit families. </p>

CC BY-SA 4.0
2019-03-06T12:31:27.207Z
If $N$ is unary, then there is a (non-uniform) function $f$ which maps $|N|$ uniquely to a solution...
dkaeae
CC BY-SA 4.0
2019-03-06T12:36:07.910Z
Is this specific to the problem being specified in unary? For example, if there were a problem that specified each instance with a different length binary input (rather than unary above), then presumably this would still hold? Apologies for potentially stupid question.
Hans Schmuber
CC BY-SA 4.0
2019-03-06T12:38:07.663Z
Yes, as long as the size of the solution is polynomially related to the instance length (for $\textbf{P}/\text{poly}$).
dkaeae
CC BY-SA 4.0
2019-03-06T12:46:25.490Z
Just to confirm, the yes was to the second question? Thanks so much for the help!
Hans Schmuber
CC BY-SA 4.0
2019-03-06T12:47:45.423Z
Of course. (How could it ever refer to the first one...?)
dkaeae
CC BY-SA 4.0
2019-03-07T07:39:55.997Z
They do not say that the language is trivially *hard* for P/poly, but that it is trivially *easy* for P/poly (i.e., that it is in P/poly). In fact, there exist no P/poly-hard languages whatsoever, because there are only countably many reductions, while P/poly has the cardinality of the continuum.
Emil Jeřábek
<cc.complexity-theory><complexity-classes><circuit-complexity><advice-and-nonuniformity>
When is a problem specified on a TM contained in non-uniform classes such as P/poly?
Hans Schmuber
# When is a problem specified on a TM contained in non-uniform classes such as P/poly?

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

In this paper by Gottesman and Irani: <https://arxiv.org/abs/0905.2419> , they prove NEXP-hardness of tiling an $N\times N$ grid. They do so by encoding a TM in the tiles making up the grid. However, they mention that the input to the TM they encode in the tiling problem must be an integer $N$ in binary rather than unary, otherwise each instance will have a different input size and hence the problem would "trivially be in P/poly" rather than NP. Hence instead they must prove the problem is NEXP-complete rather than NP-complete.

While I understand why the proof with a binary input gives NEXP-completeness, I don't understand why if $N$ is input in unary then the problem is trivially hard for P/poly? Unfortunately the model of computation they specify is in terms of TMs rather than circuits so it's not clear to me how this relates to non-uniform circuit families.

**Tags:** cc.complexity-theory, complexity-classes, circuit-complexity, advice-and-nonuniformity

> **Comments:**
> **username_1**: If $N$ is unary, then there is a (non-uniform) function $f$ which maps $|N|$ uniquely to a solution...  
> **username_0**: Is this specific to the problem being specified in unary? For example, if there were a problem that specified each instance with a different length binary input (rather than unary above), then presumably this would still hold? Apologies for potentially stupid question.  
> **username_1**: Yes, as long as the size of the solution is polynomially related to the instance length (for $\textbf{P}/\text{poly}$).  
> **username_0**: Just to confirm, the yes was to the second question? Thanks so much for the help!  
> **username_1**: Of course. (How could it ever refer to the first one...?)  
> **username_2**: They do not say that the language is trivially *hard* for P/poly, but that it is trivially *easy* for P/poly (i.e., that it is in P/poly). In fact, there exist no P/poly-hard languages whatsoever, because there are only countably many reductions, while P/poly has the cardinality of the continuum.  

---

## 2 answers

### Answer by username_3 on 2019-03-07. Score: 4 | Accepted answer

If $N$ were written in unary, then the language would be a unary language, i.e., a subset of $\{0,1\}^\*$. Every unary language is in P/poly. That's because a P/poly machine is allowed a separate advice string, one per length of the input. The advice string for length $n$ could just describe whether the input $1^n$ should be accepted or not. Or, to put it another way, P/poly allows you to specify a separate circuit per input length; so you could use the "always output no" circuit for lengths $n$ such that $1^n$ is not part of the language, otherwise the "always output yes" circuit. See <https://en.wikipedia.org/wiki/P/poly>.


---

### Answer by username_4 on 2019-03-06. Score: 2

It is always difficult to answer the question *why did the authors phrase this in such and such a way*, so I can only guess. My guess is that they assume certain background knowledge, which I now lay out.

The only input to the problem in the paper is $N$, which is given in binary, because, as the authors mention

> If instead we were given $N$ in unary, there would only be one instance per problem size

It seems intuitive that if the problem were given in unary, then the problem would be $NP$-Complete instead of $NEXP$-Complete. This intuition is wrong, because then there would be a unary $NP$-Complete language. A result of Mahany [3] says that if unary $NP$-Complete languages exist, then $P=NP$ [1]. Since the consequence $P=NP$ is believed unlikely, the unary version of the problem is probably not interesting, because nothing is believed to reduce to it. (In particular, therefore, it is of no use trying to reduce SAT to Unary-TILING)

They mention that

> there would only be one instance per problem size, and the problem would trivially be in $P/poly$.

They might mention this for the same reason as above, namely, then there would be an $NP$-Complete language in $P/poly$, and then $NP\subset P/poly$, and a result of Karp and Lipton says that it follows that the polynomial hierarchy collapses (to $PH=\Sigma\_2^P=\Pi\_2^P$, and this result has subsequently been improved [3] to $NP\subset P/poly\implies PH=S\_2^P$ and [4] to $NP\subset P/poly\implies MA=AM$). Perhaps the authors of your paper make these remarks because they assume that you are familiar with these results. If that was not the case, then you've learned something today! :)

[1] S. R. Mahaney. Sparse complete sets for NP: Solution of a conjecture by Berman and Hartmanis, Journal of Computer and System Sciences 25:130-143, 1982.

[2] R. M. Karp and R. J. Lipton. Turing machines that take advice, Enseign. Math. 28:191-201, 1982.

[3] J.-Y. Cai. S2P is contained in ZPPNP, Proceedings of IEEE FOCS'2001, pp. 620-629, 2001.

[4] V. Arvind, J. Köbler, U. Schöning, and R. Schuler. If NP has polynomial-size circuits, then MA=AM, Theoretical Computer Science 137, 1995.

> **Comments:**
> **username_5**: Uh, no, the remark about the unary language being in P/poly does not rely on Karp Lipton or anything sophisticated. EVERY unary language is in P/poly, even uncomputable ones. This is because a unary language has at most one string for every instance size $n$. So, for every $n$, you either need a circuit which always outputs 0, or a circuit that checks that the input is unary, and if it is, outputs 1.  
> **username_2**: @SashoNikolov The Karp–Lipton argument is not used in the answer to establish that the unary language is in P/poly (this seems to be taken as a given). Rather, it is used to explain *why* the authors mention this fact.  

---

