# Circuits and Closure Under Reductions

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.

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$$.
• 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. – Anon Feb 13 at 21:07