15
$\begingroup$

The remarks of the Theorem 4 in the paper "On the complexity of circuit satisfiability" claims that: if circuit satisfiability (CktSat) problem can be decided by deterministic circuits of $2^{o(n)}$ size, then ETH fails. However, there are no references and proofs for this statement in the paper, and it is hard for me to get proof of this statement.

In fact, I have tried to prove the following weaker statement but failed. "If $SAT \in P/poly$, then ETH fails."

QUESTION: How to prove that: if Circuit Satisfiability (CktSat) problem can be decided by deterministic circuits of $2^{o(n)}$ size, then ETH fails?

$\endgroup$
1
  • 7
    $\begingroup$ Its likely that what is being referred to in the paper is the nonuniform version of ETH. I have seen this mentioned elsewhere on this site. For example, see cstheory.stackexchange.com/questions/42752/… $\endgroup$
    – Nikhil
    Aug 9 '19 at 18:56

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.