6
$\begingroup$

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'.

$\endgroup$
3
$\begingroup$

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$.

$\endgroup$
  • 1
    $\begingroup$ 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. ​ ​ ​ ​ $\endgroup$ – user12859 Oct 23 '16 at 20:01
  • 1
    $\begingroup$ 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. $\endgroup$ – Ariel Oct 23 '16 at 23:04

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.