16
$\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?

Improve this question
$\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
    Commented Aug 9, 2019 at 18:56

0

Reset to default

Your Answer

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