2
$\begingroup$

Let $L$ be a language in P/poly. There is then a deterministic polynomial-time Turing machine $M$ with polynomial-sized advice that decides $L$. Consider the language $A(M)$ of all advice strings given to $M$ for instances in $L$.

Is $A(M)$ in P/poly?

Edit 2: For $A(M)$ I am envisaging a specific, unique advice language; the existence of some advice language is guaranteed by the definition of $L$, so for $A(M)$ pick any such language, such as the lexicographically smallest. Note that $A(M)$ is not necessarily decidable.

A handwaving (non-)argument for believing this goes something like this. Every unary language is in P/poly, since a single bit of advice is enough to indicate whether the input is in the language or not. In some sense advice languages are "sparsifications" of their associated languages; the advice language $A(M)$ contains a sparser representation of some of the information contained in language $L$, tweaked for the specific machine $M$. (The advice language could be exponentially sparser, if every string is an instance of the problem, but for sparse languages the advice language may actually be polynomially denser.) So it would seem to make sense that sparsifications of languages in P/poly could also be in this class.

Moreover, is there a general relationship between the complexity of $L$ and that of $A(M)$?

These seem like basic questions, so pointers to relevant literature would be appreciated if these are well-known. A counterexample for the handwaving above would also be useful!

Edit: removed a sentence that wasn't even wrong, and based on the comments from Robin and Tsuyoshi, redefined the advice language to depend on $M$ only, as $M$ already depends on $L$.

Edit 3: I think Hrushikesh captured the essential problem here, so I am accepting the answer; Tsuyoshi also said essentially the same thing in a comment. In short, $A(M)$ can be arbitrary. Any language can be fed as advice to $M$ by waiting until the input instances of the decision problem are large enough for the next piece of advice to be within the polynomial bound. This also means that I should really have asked the question in terms of a decision problem (where there are both YES and NO instances), not a language, to avoid the case where there are only finitely many YES instances.

Improve this question
$\endgroup$
5
  • 1
    $\begingroup$ It isn't clear to me that A(L,M) is uniquely specified by L and M. Could you explain that a bit more? (Unrelated: I'd recommend adding the tag advice, and removing ppoly. ppoly looks bad, and is probably too specific to be a tag.) $\endgroup$
    – Robin Kothari
    Commented Sep 25, 2010 at 17:43
  • 1
    $\begingroup$ The definition of A(L,M) is unclear to me. Are you viewing a (possibly uncomputable) sequence y_0, y_1, … of advice strings as part of the machine M and defining A(L,M) as the set {y_0, y_1, …} (forgetting which input length they correspond to)? In that case, I do not expect that there is any relation between L and A(L,M). $\endgroup$
    – Tsuyoshi Ito
    Commented Sep 25, 2010 at 17:55
  • $\begingroup$ The definition of A(M) is still unclear to me, and the previous comment still applies. Note that usually the sequence y_0, y_1, … of advice strings is not considered as part of the Turing machine. $\endgroup$
    – Tsuyoshi Ito
    Commented Sep 26, 2010 at 12:18
  • 1
    $\begingroup$ I read revision 4, and would like to point out that an advice is a sequence of strings y_0, y_1, …, not a language. The set {y_0, y_1, …} of advice strings has little to do with the nature of the advice, because this set “forgets” which i’s each string y_i came from. The following question occurred to me just now: Is your question really about advice language, or is it about the function $1^i \mapsto y_i$ (which might be called advice function)? $\endgroup$
    – Tsuyoshi Ito
    Commented Sep 27, 2010 at 14:39
  • $\begingroup$ @Tsuyoshi: In this question I was envisaging the advice language of advice strings, forgetting which input length each string is associated with. The advice function $\{(i,A(M)(i)) \mid i \in \mathbb{N}\}$ that you suggest, mapping each input length $i$ to the string for the inputs of that length, would probably be an interesting object itself. However, the advice function wasn't what I had in mind here. $\endgroup$
    – András Salamon
    Commented Sep 27, 2010 at 15:13

1 Answer 1

Reset to default
5
$\begingroup$

Rigorous and probably more correct version at the bottom.

I don't think so. Consider the case where A(L,M) consists of advice strings of even length. To decide if x is in L, the machine M gets advice yz where y and z are strings of equal length. M discards z and decides membership of x in L only depending on y. Let y be of length n, and let z range over some arbitrary subset S of strings of length n.

In such a case, A(L,M) cannot be in P/Poly since given a string yz, the machine has to test membership of z in S. But since the advice is of length poly(n), the machine cannot work correctly for every S by counting argument.

Another more rigorous version:

Let L be the trivial language containing all strings. The machine M ignores its advice and accepts every input. The task is now to construct the set of advice strings A(M) which cannot be in P/Poly subject to the constraint that strings in L of length $n$ get advice of length $O(poly(n))$.

For every length $i$, let $S_i \subseteq {0,1}^i$. Let $S = \cup_i S_i$. Construct a mapping $f: S \rightarrow Z^+$ such that $|s| \leq f(s)$. The mapping just enumerates the strings in $S$ in non-decreasing order of length. The string $s$ serves as advice to M for strings of length $f(s)$.

By choosing $S_i$ to be of superpolynomial description size (can be done because of counting arguments), we get that $S$ (which is also $A(M)$) lies outside P/Poly.

Improve this answer
$\endgroup$
6
  • $\begingroup$ @Hrushikesh Tila: OK, I think I see what you mean. Instances of $L$ of length $n$ receive advice of length $2p(n)$; the second part of the advice is from a hard language. But by a (different) counting argument, isn't it the case that the language of advice is sparse itself, so the part of S that has size $n$ can be described using only polynomially many bits? At least this is the kind of argument that is intended by the handwaving. I'd appreciate someone pointing out my error! $\endgroup$
    – András Salamon
    Commented Sep 25, 2010 at 22:01
  • $\begingroup$ @Andras: What we need is that there are several advice strings of the form yz, yz', yz'', etc. One way to achieve this is with the trivial language L containing all strings. The advice will be of the form y=1^n, and z will range over all strings of length n. The machine will just ignore the advice and accept every string. To get around the "sparsity" problem, we just need a way to map all these advice strings to different integer lengths. This is possible because there exists a (non-uniform) bijection from all finite subsets of integers to the set of integers such that len(advice)=O(poly(n)). $\endgroup$
    – Hrushikesh
    Commented Sep 25, 2010 at 22:39
  • $\begingroup$ Argh, can no longer edit the comment. The advice is of the form yz=(1^m)z where m=O(poly(n)) and n is the size of the input. $\endgroup$
    – Hrushikesh
    Commented Sep 25, 2010 at 22:47
  • $\begingroup$ @Hrushikesh: Your key point seems to be that there are $2^{N/2}$ different strings in $A(M)$ for every size $N = 2m$. But this is superpolynomial. I am intrigued -- could you sketch the bijection you have in mind? $\endgroup$
    – András Salamon
    Commented Sep 27, 2010 at 15:02
  • $\begingroup$ @Hrushikesh: Perhaps a simpler argument is this: the advice string just has to be shorter than $p(n)$. So pick any language $K$ that is outside $P/poly$, then feed it to $M$ deciding the trivial language of all strings (as you suggest), in the following way. Suppose the strings of $K$ are enumerated in increasing size. If the $i$th string in $K$ is $s_i$, then provide $s_i$ as advice to all inputs with $b$ bits, $2^i \le b \lt 2^{i+1}$. If $K$ is very sparse, then adjust the interval; it is enough that the function mapping the index in $K$ to size is non-decreasing. $\endgroup$
    – András Salamon
    Commented Sep 27, 2010 at 15:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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