1
$\begingroup$

Theorem: (Stockmeyer, 1974) Any circuit that takes as input a formula (in the language of WS1S) with up to 616 symbols and produces as output a correct answer saying whether the formula is valid or not, requires at least $10^{123}$ gates.

Suppose we have generalized theorem: Any circuit that takes as input a formula with up to $n$ symbols and produces as output a correct answer saying whether the formula is valid or not, requires at least $10^n$ gates. Is this true that this theorem equivalent to statement that P is not equal to coNP?

$\endgroup$
1
  • 2
    $\begingroup$ I'm not sure how your title relates to your question. $\endgroup$ Commented Feb 27, 2018 at 16:26

1 Answer 1

3
$\begingroup$

The theorem is false. There is a circuit of size $\tilde{O}(2^n)$ that solves SAT. At any rate, the relevant conjectures you would be proving using statements of this form are the Exponential time hypothesis and its variants.

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.