27
$\begingroup$

I want to know if non-uniformity helps computing functions in practice. It is easy to show that there are functions in $P/poly - P$, take any uncomputable function $f$ and consider the language {$0^{f(n)}:n\in \omega$}, which clearly has simple non-uniform circuits, but is not computable uniformly at all, but this is not the kind of functions I am interested in.

Is there a function that we know it can be computed non-uniformly but we don't know if it can be computed uniformly (or at least proving that it can not be computed uniformly is not obvious)?

How can non-uniformity of circuits be used for computing functions that are not known to be computable uniformly (with almost the same amount of resources)?

Please note that I don't want pathological functions like uncomputable one mentioned above, I want natural functions that people are really interested in computing and it is plausible that can be or could have been computed uniformly.

Edit: I know that $BPP \subseteq P/poly$. So an answer which is not a derandomizations result is more interesting for me.

Edit 2: As András Salamon and Tsuyoshi Ito have said in their answers, $Sparse \subset P/poly$, and there are interesting problems in $Sparse$ that are not known to be in $P$, so formally they have answered what I have asked, but that does not help with what I am really interested in since the reason that they are in $P/poly$ is the possibility of hard coding a sparse language into the circuit. A language which is not sparse would be more interesting.

$\endgroup$
  • $\begingroup$ @András Salamon, @Tsuyoshi Ito: Thank you. But what I am interested in is to understand how non-uniformity can help in computing functions. The fact that sparse languages are in $P/poly$ does not help with it, they are in $P/poly$ simply because we can "hard code" them into the circuit. I should have added the requirement to my question that "the language is not trivially in $P/poly$". $\endgroup$ – Kaveh Sep 26 '10 at 13:51
13
$\begingroup$

I do not know if this satisfies your requirements, but Bill Gasarch’s blog post in July 2010 asks about languages in SPARSE∩NP which are not thought to be in P, giving an example from Ramsey Theory. Any such languages belong to (P/poly)∩NP.

Related to this, For any language L∈NP, the language TL={1n: L contains some string of length n} is in TALLY∩NP ⊆ SPARSE∩NP ⊆ (P/poly)∩NP. Depending on the choice of the language L, TL may not have an obvious reason to belong to P.

$\endgroup$
8
$\begingroup$

Tsuyoshi Ito's elegantly sparse phrasing in another answer does not explicitly say so, but perhaps it is worth pointing out: any sparse language is in P/poly. Then also any tally language is in P/poly (as every tally language is sparse).

So one way to find "natural" languages in P/poly but not in P, is to look for "hard" sparse languages. As you point out, the "hardest" are the undecidable ones when encoded in a sparse way, for instance in unary. More generally, the unary encoded version of any language outside EXP will then be outside P. (If not, then consider the exponential-time Turing machine that generates the unary encoding, composed with the machine that solves the resulting unary-encoded language in time that is polynomial in the unary encoding. This is exponential in the size of the original instance. The overall machine then runs in exponential time.) Some handy 2-EXP-complete language might then suit your taste as a "natural" problem.

Note that Bill Gasarch's sparse Ramsey-theoretic language seems to fall into the category of languages constructed by sparsifying a hard language. If one encodes the instance as a triple of binary numbers instead of two unary and one binary, then the colouring is no longer of polynomial size, so the language is not obviously in NP.

$\endgroup$
6
$\begingroup$

This is more like a comment in response to the revised question (revision 3) than an answer, but it is too long for a comment.

Simply excluding sparse languages is not enough to exclude languages like {x∈{0,1}*: |x|∈S} instead of {1n: nS}, where S is an infinite subset of {0, 1, 2, …}. I would like to point out that it may be difficult to distinguish between the case where a language belongs to P/poly because it is “essentially sparse” (such as {1n: nS} and {x: |x|∈S}) and the case where a language belongs to P/poly for other reasons. The problematic thing here is, obviously, how to define the term “essentially sparse.”

You may want to define “essential sparseness” as follows: a language is essentially sparse if it is reducible to a sparse language. However, care must be taken because if you use the polynomial-time Turing reducibility in this definition, the definition is equivalent to the membership to P/poly!

So an obvious thing to try is to use the polynomial-time many-one reducibility. I do not know whether this is equivalent to the membership to P/poly, let alone whether P/poly contains any natural language which is not essentially sparse in this sense.

$\endgroup$
  • $\begingroup$ Actually I thought about this when I saw the answers before modifying the question, as it was natural to think of boolean combination of sparse languages. I thought that excluding languages which are $AC^0$ reducible to sparse languages (or maybe a little bit more) should be enough for my question, but it seems that this is more involved than I thought. $\endgroup$ – Kaveh Sep 26 '10 at 15:20
  • $\begingroup$ @Kaveh: That may be another good definition for “essentially sparse.” Reading your comment, I wonder whether P/poly = P∪(AC0/poly) (I guess not), because any problem in (P/poly)∖(P∪(AC0/poly)) could be arguably said to be “computable by using a nonuniform family of polynomial-size circuits by really combining the power of polynomial-size circuits and the power of nonuniformity.” $\endgroup$ – Tsuyoshi Ito Sep 26 '10 at 23:17
  • $\begingroup$ A possible problem with my definition based on one of your examples is whether the following language is essentially sparse: check if the number of ones in the input is in a sparse language $S$. (More generally, let $f$ be a complete function problem for complexity class $C$ and let $S$ be a sparse language. Think of $f$ as having a large range similar to the NumOnes function. Let $L$ be the set of $x$s s.t. $f(x) \in S$.) $\endgroup$ – Kaveh Sep 26 '10 at 23:54
  • $\begingroup$ [continued] Another class of languages: take a sparse language $S$ and language $A$ complete for complexity class $C$ and then consider the concatenation $L=A'.01.S'$ ($A'$ is $A$ where each symbol is replaced with two copies of it, e.g. 010 becomes 001100). One may also require that the length of second part in the concatenation is less than the length of first part. These languages satisfy all of the conditions except being a natural problem that people are really interested in solving. $\endgroup$ – Kaveh Sep 27 '10 at 0:08
  • $\begingroup$ @Kaveh: Hmm, I see. Thanks for sharing the examples. I withdraw the idea of viewing (P/poly)∖(P∪(AC0/poly)) as “P/poly for nontrivial reasons.” If I am not mistaken, both of your examples are polynomial-time many-one reducible to a sparse language, so there is still some hope that the definition of “essential sparseness” I suggested in the answer might be suitable. $\endgroup$ – Tsuyoshi Ito Sep 27 '10 at 0:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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