1
$\begingroup$

Suppose that $A$ and $B$ are languages such that $A\leq_P B$ (many-to-one Karp reduction), and $B\in \mathbf{P/poly}$. How do we prove that $A\in\mathbf{P/poly}$?

Using similar ideas like Cook-Levin (or $P\subseteq \mathbf{P/poly}$), I can show that given $x\in\{0,1\}^n$, there exists a (easily computable) poly-sized circuit that can compute each bit of the reduction, say $R(x)$. The issue for me is that the size of $R(x)$ may depend on $x$ and not only $n$ (since we only require it to be bounded by $\mathrm{poly}(n)$). In such a case, it is not clear how to what input length circuit for the language $B$ to use.

$\endgroup$
0
$\begingroup$

If $A \leq_P B$ then since $P \subseteq P/\mathit{poly}$, also $A \leq_{P/\mathit{poly}} B$. This means that there is a function $f \in P/\mathit{poly}$ such that $x \in A \leftrightarrow f(x) \in B$. Since $f \in P/\mathit{poly}$, for every $n$ there is a polynomial size circuit $C$ that computes $f(x)$ for $x$ of length $n$. The circuit needs to have some mechanism for indicating the output length, which might depend on $x$.

Since $C$ has polynomial size, in particular, there are only polynomially many options for the output length, and so if $B \in P/\mathit{poly}$, these circuits can be connected to the outputs of $C$ in order to compute $A$.

$\endgroup$
2
  • $\begingroup$ Thanks. As I mentioned, I understand this. My issue is that the size of $f(x)$ may be dependent on $x$ (and not only on $n$), and so it is not clear which sized circuit for $B$ to use after doing this reduction. $\endgroup$ – Anon Feb 13 at 21:07
  • $\begingroup$ This is not a big problem. I updated my answer, but perhaps it is better if you spent more time on it yourself. $\endgroup$ – Yuval Filmus Feb 13 at 21:11

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.