All Questions
3
questions with bounties
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 ...
