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.

  • 3
    $\begingroup$ If $N$ is unary, then there is a (non-uniform) function $f$ which maps $|N|$ uniquely to a solution... $\endgroup$ – dkaeae Mar 6 '19 at 12:31
  • $\begingroup$ 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. $\endgroup$ – user138901 Mar 6 '19 at 12:36
  • 2
    $\begingroup$ Yes, as long as the size of the solution is polynomially related to the instance length (for $\textbf{P}/\text{poly}$). $\endgroup$ – dkaeae Mar 6 '19 at 12:38
  • 1
    $\begingroup$ Of course. (How could it ever refer to the first one...?) $\endgroup$ – dkaeae Mar 6 '19 at 12:47
  • 2
    $\begingroup$ 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. $\endgroup$ – Emil Jeřábek Mar 7 '19 at 7:39

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.

| cite | improve this answer | |

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.

| cite | improve this answer | |
  • 2
    $\begingroup$ 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. $\endgroup$ – Sasho Nikolov Mar 6 '19 at 22:47
  • $\begingroup$ @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. $\endgroup$ – Emil Jeřábek Mar 7 '19 at 7:37

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