4 ms·

tl,dr version of his strategy (as far as I understood it) 1. For a fixed permutation construct a Viterbi-like search on the triplet assignments - if it fails i

by mitko 16y ago

tl,dr version of his strategy (as far as I understood it) 1. For a fixed permutation construct a Viterbi-like search on the triplet assignments - if it fails it is not satisfiable. However, if it doesn't fail right away, there is still no guarantee there is an assignment. Call this structure compact triplet (CTF) or whatever. 2. Constuct a small set of permutation (at most m) for which every clause in the original CNF failing to satisfy will mean that at least one of these permutations CTFs will fail to satisfy. 3. Efficiently? combine the structures. I didn't really read it deeply but that from what I understood that seems to be the top level strategy. I'm not 100% certain about it.

DrJosiah 16y ago
That's more or less what I got out of it as well, though I came at it from the other direction... If you skip the first part about pre-processing, and instead look at the graph that is generated, you can come up with following: 1. There exists a graph consisting of potential truth assignments on N unknowns in M clauses consisting of 7M nodes, and <48M2 edges. 2. Label each node uA,uB,uC,vA,vB,vC where u? is the unknown number, and v? is whether that unknown is true or false. 3. Edges exist between node I and node J if either nodes I and J share zero unknowns, OR both I and J share at least one variable AND all shared variables have the same value. 4. For there to be an assignment that causes the full statement to be correct, you must find an M-clique (a complete graph on M nodes within the 7M node graph). Solving part 4 is NPC. His claim is, basically, that if you permute/partition the input (to construct the tables), you can construct a disconnected graph with far fewer edges (get rid of the first part of #3 above), then add links graphs in such a way that if you can find a path from a tier-1 node to a tier-2 node, ..., to a tier-M node, examining the labels is sufficient to solve the problem. The two nasty parts are finding an efficient permutation/partition step, then managing to properly link the disconnected graphs. As you say, the two steps that the author hand-waves.

by mitko 16y ago

DrJosiah 16y ago

That's more or less what I got out of it as well, though I came at it from the other direction... If you skip the first part about pre-processing, and instead look at the graph that is generated, you can come up with following: 1. There exists a graph consisting of potential truth assignments on N unknowns in M clauses consisting of 7M nodes, and <48M2 edges. 2. Label each node uA,uB,uC,vA,vB,vC where u? is the unknown number, and v? is whether that unknown is true or false. 3. Edges exist between node I and node J if either nodes I and J share zero unknowns, OR both I and J share at least one variable AND all shared variables have the same value. 4. For there to be an assignment that causes the full statement to be correct, you must find an M-clique (a complete graph on M nodes within the 7M node graph). Solving part 4 is NPC. His claim is, basically, that if you permute/partition the input (to construct the tables), you can construct a disconnected graph with far fewer edges (get rid of the first part of #3 above), then add links graphs in such a way that if you can find a path from a tier-1 node to a tier-2 node, ..., to a tier-M node, examining the labels is sufficient to solve the problem. The two nasty parts are finding an efficient permutation/partition step, then managing to properly link the disconnected graphs. As you say, the two steps that the author hand-waves.