# prove that if $SAT\notin Size(2^{n/100})$ then CorrectSATSolver$\in P$

I need to prove that if $$SAT\notin Size(2^{n/100})$$ then CorrectSATSolver$$\in P$$.

Where CorrectSATSolver $$= \{C | C(\varphi) = 1 \iff \varphi$$ is satisfiable$$\}$$. In other words, CorrectSATSolver problem is as follows: Given a circuit C, decide if the circuit C solves the SAT problem.

I don't understand how to use the assumption.

I have already proven in class thet CorrectSATSolver $$\in coNP$$, I'm not sure if it helps.

I would very appreciate any help. Thank yoy

• What is the definition of $Size(f(n))$? Apr 18, 2022 at 21:39
• This is a nice puzzle. I suggest spending a few more hours on it. The solution is very short. Apr 19, 2022 at 5:16
• @plshelp Size(f(n)) is the set of decision problems that can be solved by f(n)-sized circuit families.
– ORN
Apr 19, 2022 at 9:33
• @YuvalFilmus Can you give me a hint please?
– ORN
Apr 21, 2022 at 13:24
• Consider two cases: $C$ is small and $C$ is large. Apr 21, 2022 at 13:52

If $$|C| < 2^{n/100}$$ then $$C \not\in \text{CorrectSATSolver}$$ since otherwise we would have $$\text{SAT} \in \text{Size}(2^{n/100})$$.
Assume then that $$|C| \ge 2^{n/100}$$. Evaluating $$C$$ for a fixed assignment requires time $$|C|$$ and there are at most $$2^{n}$$ possible distinct truth assignments to a formula of size $$n$$. Therefore $$\text{CorrectSATSolver}$$ can be decided in time $$O(2^{n} \cdot |C|) = O((2^{n/100})^{100} \cdot |C|) \subseteq O(|C|^{101})$$ by exhaustively checking the output of $$C$$ for all possible assignments.