Hot answers tagged

1

I'm afraid that the answer to all your questions is false: There are languages decided by constant size circuits which aren't decidable. It is conjectured that $\mathsf{NC^1} \neq \mathsf{P}$. It is conjectured that $\mathsf{NP} \neq \mathsf{coNP}$.


Only top voted, non community-wiki answers of a minimum length are eligible