Is there a candidate for a natural problem in $P/poly - P$?

Question

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.

Answer 1

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 T_L={1ⁿ: L contains some string of length n} is in TALLY∩NP ⊆ SPARSE∩NP ⊆ (P/poly)∩NP. Depending on the choice of the language L, T_L may not have an obvious reason to belong to P.

Answer 2

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.

Answer 3

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 {1ⁿ: n∈S}, 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 {1ⁿ: n∈S} 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.