16

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?

Jacobs
  • 161
  • 4
  • 7
    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 https://cstheory.stackexchange.com/questions/42752/is-there-a-relation-between-bbh-black-box-hypothesis-and-seth-strong-exponent – Nikhil Aug 09 '19 at 18:56

0 Answers0