0
$\begingroup$

I am going through Justin Thaler's book - https://people.cs.georgetown.edu/jthaler/ProofsArgsAndZK.pdf - "Proofs, Arguments, and Zero-Knowledge"

He presents the Sumcheck protocol & then claims on Page 41 that the interactive Sumcheck protocol helps solve the SAT problem in better than exponential time.

What Sumcheck does is

$H = \sum_{b_1 \in \lbrace 0,1 \rbrace} \space \sum_{b_2 \in \lbrace 0,1 \rbrace} \space ... \space \sum_{b_v \in \lbrace 0,1 \rbrace} g(b_1, b_2,...,b_v)$

However, this is summing up all the total of all possible values the circuit can evaluate to. How does that give you the values which with satisfy the circuit?

$\endgroup$

1 Answer 1

2
$\begingroup$

It doesn't solve SAT in faster than exponential time. It solves #SAT (not SAT), and the prover still needs exponential time.

It doesn't give you the values which satisfy the circuit. It doesn't need to. #SAT doesn't ask you to find the values that satisfy the circuit. It asks for a count of the number of satisfying assignments, i.e., assignments that satisfy the formula. $g$ is chosen so that $g(b_1,\dots,b_v)$ is 1 if the assignment $b_1,\dots,b_v$ satisfies the formula, or 0 otherwise. Summing those up counts the number of assignments where it is 1, i.e., the number of satisfying assignments.

$\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.