If a Sparse Language is NP complete, then are all languages in NP in P/poly? I know that sparse languages are in P/poly, but does a polynomial time reduction give an addition to the circuit that is super polynomial? A sparse language is such that $\forall n \in \mathbb{N}, |L \cap \{ 0,1 \} ^{n} | \leq p(n)$ for some polynomial $p(n)$.
$\begingroup$
$\endgroup$
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
Yes, see Mahaney's theorem. It states that if a sparse language is $\mathbf{NP}-$complete, then $\mathbf{P=NP}$, and since $\mathbf{P\subseteq P_{poly}}$, then $\mathbf{NP\subseteq P_{poly}}$
