7 ms·
> For a clause like x_1 OR x_2 OR x_3, we think of it as “the only forbidden combination is x_1 = \text{FALSE},\; x_2 = \text{FALSE},\; x_3 = \text{FALSE}.” Our
by jstanley 2y ago
> For a clause like x_1 OR x_2 OR x_3, we think of it as “the only forbidden combination is x_1 = \text{FALSE},\; x_2 = \text{FALSE},\; x_3 = \text{FALSE}.” Our task is to construct a gadget that eliminates this one forbidden combination while allowing all others. Here’s how: if both x_1 and x_2 are false (represented as the edge being colored red-blue), the node labeled x_1 OR x_2 must be blue. Similarly, the node labeled x_1 OR x_2 OR x_3 must be blue. You can verify that any other combination is acceptable.
I didn't follow this. I also looked at the graph and found that the node labeled "x1 OR x2 OR x3" is in fact connected to a blue node, so it can't be blue?
I didn't manage to work out how the clause gadget is meant to work so I can't tell if the graph is wrong or the explanation.
> Our zero-knowledge proof was interactive—a back-and-forth conversation between the prover and the verifier.
I think possibly the section containing your zero knowledge proof got edited out by accident?
- CJefferson 2y agoThe graph explanation is saying: The 'x1 or x2 or x3' node can't be blue (as you say, it's connected to a blue node!) It doesn't take too long to convince yourself that if we coloured the right-hand node of x1, x2 and x3 all blue, there is no valid colouring of the 'clause 1' bit of the graph where the 'x1 or x2 or x3' node is not blue -- which means there is no colouring of the whole graph. On the other hand, if I make at least one of the right-hand nodes of x1, x2 or x3 red, then I can colour the 'clause 1' bit of the graph such that the 'x1 or x2 or x3' node isn't blue, so all is fine! They are trying to explain that this graph correctly represents the SAT problem, because it has a valid colouring if and only if the SAT problem has a solution -- and we do this by checking the clauses one at a time.
- jstanley 2y agoThanks.