# On complete problems for $P/poly$ and $BPP$

Is there a complete problem for $P/poly$?

Decision version of permanent more or less acts as a complete problem for $PP$ while its weaker sibling has no known complete language. Why? I saw wiki reason but it is not clear to me. In https://en.wikipedia.org/wiki/PP_(complexity)#Complete_problems_and_other_properties it is stated 'Unlike BPP, PP is a syntactic, rather than semantic class. Any polynomial-time probabilistic machine recognizes some language in PP. In contrast, given a description of a polynomial-time probabilistic machine, it is undecidable in general to determine if it recognizes a language in BPP'.

• – Ariel Oct 22 '16 at 20:32

There are no $P/Poly$ complete languages (relative to polynomial time or even computable reductions).

Suppose for the purpose of contradiction that there exists some language $L$ which is complete for $P/Poly$. In that case the mapping $f:P/Poly\rightarrow \mathbb{N}$, which maps any language in $P/Poly$ to its corresponding reduction to $L$ (we refer to the encoding of this reduction as a natural number), is an injection from $P/Poly$ to the natural numbers. This of course leads to a contradiction, since $P/Poly$ is of cardinality $2^{\aleph_0}$.

In light of Ricky Demer's comment, we should note that since computable reductions are of no use to $P/Poly$, one needs to introduce the notion of non-uniform reductions. One example is projection reductions.

A family of boolean functions $f_n(x_1,...,x_n)$ is said to be projection reducible to the family $g_n(y_1,...,y_n)$ if for all $n\in\mathbb{N}$ there exists some $m\le p(n)$ with polynomial $p$, and a rewiring of $g$'s inputs, $\sigma:\left\{y_1,...,y_m\right\}\rightarrow\left\{0,1,x_1,\overline{x_1},...,x_n,{\overline{x_n}}\right\}$, such that $f_n(x_1,...,x_n)=g_m\left(\sigma(y_1),...,\sigma(y_m)\right)$. Intuitively, this means that given a circuit for $g$ (perhaps with polynomialy more inputs), we can compute $f$ just be rewiring the inputs accordingly. We denote this by $f\le_{proj} g$.

Note that if $g\in P/Poly$ and $f\le_{proj} g$ then $f\in P/Poly$, the advice for input $x$ would be the rewiring $\sigma$, together with the $m(|x|)$ inputs circuit for $g$.

The following is a (very) short sketch of the proof that the circuit value problem, $CVP$, which takes as input a circuit $\mathcal{C}$ and input $x$, and asks whether $\mathcal{C}(x)=1$ is $P/Poly$ hard under such reductions. Given $L\in P/Poly$, let $\mathcal{C}_n$ be the polynomial circuit family for $L$. For any string $x$, You can hardwire $\mathcal{C}_{|x|}$ as input to $CVP$ (using the constants $0/1$), and use the rest of the variables to input $x$.

• Thus, for P/poly-hardness, one needs non-uniform reductions. ​ I'm pretty sure the Circuit Value Problem is P/poly-hard under non-uniform monotone projections. ​ ​ ​ ​ – user12859 Oct 23 '16 at 20:01
• Thank you. Since computable reductions are not of interest here, we should indeed look for other forms of reductions. I edited my answer to add some information on projection reductions. – Ariel Oct 23 '16 at 23:04