1
$\begingroup$

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

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

1 Answer 1

Reset to default
0
$\begingroup$

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.

Improve this answer
$\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.