COMS 482: unofficial class blog

PSPACE = {x | x has a polynomial space algorithm}

Given T = c1 ^ c2 ^ … ^ ck where each clauses c_i is an OR-clause with 3 terms (an instance of 3-SAT) , does there exist and x1 for all x2 does there exist an x3 for all x4 … for all xn-1 such that T is true? This is called quantified 3-SAT (QSAT), an is a kind of alternation thatsshows up in many game AI questions. I.e., is there a move for me such that for all of my opponents’ next move there is another good move for me such that … etc.

One idea for QSAT–try all truth assignments. Define: p^w = polynomial time algorithm given an “oracle” for w. What if you need a solution to an NP-complete problem? Sometimes there are special characteristics of a problem that allows a solution. Sometimes we can define a provably good approximation solution!

Look at vertex cover. Given G, k, is there a vertex cover of size <= k? So, there are n choose k possible vertex covers. We could try them all, but… that’s a lot of options. To check a vertex cover, try each edge e, see if at least one endpoint is in the cover, and repeat. This takes O(n²) time.

Claim: “If G has n nodes, with max-degree d, and if there is a vertex cover of size k, then G has at most k*d edges.”

k*d is better than O(n²). Let s be the vertex cover with |s| = k. There are at most d edges from each vertex in S, there are at most k*d places where S touches some edge either once or twice. |E| <= # touches <= k*d, so trying all the possibilities is no longer O(n choose k * k * (n-1)) but rather O(n^k+1 * k).

Observe that any graph with more than k*(n-1) edges cannot have a vertex cover of size k, and if there is a vertex cover of size k and we completely remove a vertex from the cover, then the remaining graph has a vertex cover of size k-1.

Find(G, k):
    if G has no edges return false
    if G has more than k*(n-1) edges return false
    choose e = (u, v)
        s1 = find(G - {u}, k-1)
        s2 = find(G - {v}, k-1)
        if s1 and s2 fail, then return false
        if(s1) return s1 + {u}
        if(s2) return s2 + {v}

This algorithm is O(k*n*2^k+1). The proof is left as an exercise to the reader.

Recall that we write “x is in P if there exists a polynomial time algorithm a(*) such that s is in x if and only a(s) returns yes.” Define x’ = { s | s not in x}. Is x’ in P? Yes, because we can define a’(*) as follows:

if a(s) returns “yes” then return “no” otherwise return “yes”

Let y be in NP. What about y’? Let y’ = {s | s not in y}. To say “y is in NP” means that there exists a polynomial time certifier b(*,*): s is in y if and only if there exists t such that b(s, t) returns “yes,” in polynomial bounded size. So, let’s look at y’:

s in y’
<=> s not in y
<=> ! there exists t such that b(s,t) returns “yes”
<=> for all t, b(s, t) returns “no”

Co-NP = {y’ | y is in NP}. Does NP = Co-NP? We don’t know. If we assume P=NP, though, it follows that P=Co-NP as well. Generally the consensus is that NP does not equal Co-NP. Here is a diagram that might help explain P, NP, Co-NP, and PSPACE:

P-SPACE is defined as {x | x has an algorithm using at most polynomial space}. P is a subset of PSPACE, because you cannot use more than polynomial space in only polynomial time. To say x is in PSPACE implies that x’ is in PSPACE using the same inversion algorithm as above. You can also create the following chain:

x in Co-NP => x’ in NP => x’ in SPACE => x in PSPACE

The Travelling Salesman Problem (TSP):

Given distances between n cities and a bound D, is there a tour (visit all cities and return home) of cost at most D? Note that using TSP to prove NP-completeness of other problems is quite hard.

Claim: “TSP is NP-complete”

Proof: TSP is in the set NP. Given a valid tour, we can check that it is valid and has a cost &lt= D in polynomial time. Then, we want to show that Hamiltonian Cycle reduces to TSP in polynomial time. Given an HC problem as a graph G, we can show how to build the travelling salesman problem. Using the same vertices, place an edge between each pair with cost 1 if the edge exists in G, otherwise place the edge with cost 2.

Claim: “G has a Hamiltonian Cycle if and only if G’ has a TSP tour of cost &lt= n (vertices)”

Proof (=>): Assume G has a HC. Then the cycle in G’ is a tour and its cost is <= n.

Proof (<=): Assume G’ has a TSP tour of cost <= n. Every node is visited, and each edge has cost 1. The corresponding cycle is a valid HC.

3D Matching:

Given disjoint sets X, Y, and Z each of size n and given a set of triples T is a subset of (X, Y, Z) is there a subset of T of size n that covers all X + Y + Z? We can show that 3-SAT reduces to 3D Matching in polynomial time, so 3D matching is NP-complete.

Graph Coloring:

A graph g is said to have a k-coloring if there is a way to assign colors to vertices such that all adjacent verticex do not share the same color. Given a graph g and a bound k, is G k-colorable? Graph coloring is NP-complete, but on planar graphs 2-coloring has a simple DFS algorithm, and >=4-coloring simply returns “yes.”

Subset Sum:

Given w₁, … , w_n in {Naturals} and a target w_i is there a subset of w₁, … , w_n whose sum is exactly w_i?

NP-Complete “Types”:

All the NP Complete problems we have covered so far can be grouped by similarity into the following categories:

• Packing problems: Set Packing, Independent Set
• Covering problems: Vertex & Set Cover
• Partitioning problems: 3D Matching, Graph coloring
• Sequencing problems: Hamiltonian Cycle, Hamiltonian Path, Travelling Salesman Problem
• Numerical problems: Subset sum
• Constraint problems: SAT, 3-SAT, and Circuit-SAT

Hamiltonian Cycle Problem:

Given a graph G, is there “a path that visits each vertex once and return to the start,” i.e. a Hamiltonian Cycle?

Claim: “Hamiltonian Cycle is NP-complete.”

Proof: Hamiltonian Cycle is in NP because a given list of vertices can be checked for a tour in polynomial time. Now, we want to show that 3-SAT reduces to Hamiltonian Cycle in polynomial time. Thus, we need some way of mapping the variables and clauses to a hamiltonian cycle problem graph:

While this graph is complex at first, look at how it is built. For each variable, there is a row of at most 2n nodes, where n is the number of clauses. Two of these nodes are connected to each clause if the variable appears in that clause. The ends of each row of nodes are connected to the ends of the next. Walking left to right down a row means “true,” while right to left means “false.” In this way, a Hamiltonian cycle through the graph represents an assignment of truth values to the variables in a list of 3-SAT clauses.

Claim: “The 3-SAT boolean formula is satisfiable if and only if the graph has a hamiltonian cycle.”

Proof (=>): Assume the formula is satisfiable by some truth assignment. Choose one true term in each clause, traverse the graph moving across each variable’s path in the appropriate direction, and take a diversion to a clause node for each term chosen above. This path is a Hamiltonian cycle.

Proof (<=): Suppose there exists a Hamiltonian cycle c that traverses a variable’s row either left to right or right to left. Call one way true, and the other false. Ecah clause node is visited by a side-trip from a variable row. This variable corresponds to a true term in the clause.

External Links:

• Hamiltonian cycle
• Traveling salesman problem

Did you know you can read the CS482 Blog on Bloglines? Just click the button: