New answers tagged

0

If you want to reduce Clique directly to 3SAT, you can design a boolean circuit, where the input is a graph and a subset of vertices, and the output is TRUE if that subset is a clique and FALSE otherwise. If the graph has N vertices, you need: N variables, one for each vertex, which is TRUE if it is part of the subset and FALSE otherwise. N * (N - 1) ...


0

Your evaluation only works into one direction, you can use it to test for unsatisfiability for the listed cases which are only a subset of all unsatisfiability cases. Imagine for example a formula in which 100 clauses contain x and one clause contains (¬x ∨ ¬x ∨ ¬x).


Top 50 recent answers are included