Consider $\mathcal P(n,m)$ to be a class from the set $\{k\mbox{-}\mathsf{SAT}(n,m),\mathsf{CIRCUITSAT}(n,m)\}$ where $k$ is fixed, $n$ is number of variables and $m$ is number of clauses.

Denote $\mathsf{MCSP}[s(t)]$ to the class of problems which have a circuit of size $s(t)$ when input a truth table of size $t$

What is the best reduction that we know from a member in $\mathcal P(n,m)$ to $\mathsf{MCSP}[s(t)]$ when $t=f(n)$ for a function $f:\mathsf{Z_{\geq0}}\rightarrow\mathsf{Z_{\geq0}}$?

I am looking for the correct parametrization between the problems that we know (best $s(t)=s(f(n))$).

I know some reductions provide separation such as $\mathsf{EXP}\neq\mathsf{ZPP}$ or $\mathsf{PSPACE}\neq\mathsf{ZPP}$ or $\mathsf{NP}\not\subseteq\mathsf{P/poly}$. Literature says these are $\mathsf p$, $\mathsf{LOGSPACE}$ or $\mathsf{AC}^0$ reductions respectively and the question is what would the parameters of $f$ and $s$ be?


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.