All Questions

Filter by
Sorted by
Tagged with
7
votes
1answer
143 views
+50

Clarification of Theorem 1.11 in the book Computational Complexity by Arora/Barak

The book Computational Complexity: A Modern Approach by Arora/Barak provides the following: Theorem 1.10 There exists a function $UC: \{0,1\}^* \to \{0,1\}$ that is not computable by any TM. ...
7
votes
2answers
670 views
+100

SAT algorithm for determining if a graph is disjoint

What are some good algorithms to have a SAT (CNF) solver determine if a given graph is fully-connected or disjoint? The best one I can think of is this: Number the nodes 1..N, where N is the number ...
1
vote
1answer
44 views
+100

SAT formula for connected graphs on the grid

In the answer to an earlier question "SAT algorithm for determining if a graph is disjoint" a formula is constructed that is satisfiable iff a given graph is connected. The formula uses a ...