Any $\mathsf{NC}$ circuit could be presented in SAT form via Tseytin transform. This applies in the reverse too: an arbitrary SAT instance could encode any $\mathsf{NC}$ circuit.

Now, Frege proof system is said to be limited with $\mathsf{NC_1}$ circuits. In that case, does it mean that $\mathsf{NP=coNP}$ iff there exists a non-deterministic polynomial time reduction from any given $\mathsf{NC}$ circuit to an $\mathsf{NC_1}$ circuit? Or is it still possible that $\mathsf{NC_1\subsetneq NC}$ and $\mathsf{NP=coNP}$?



Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.