2. P (8 points) Prove that each of following problems is in P by sketching a pol

Question

2. P (8 points)

Prove that each of following problems is in P by sketching a polynomial time algorithm that solves it. Briefly justify that your algorithm runs in polynomial.

(1) EASY-SOLUTION = {F | F is a formula in 3cnf which is satisfied by assigning the same truth value to all of its variables (i.e., all variables are true or all variables are false)}

(2) LARGE-SUBSET = {S,k,t | S = {x1,...,xn} is a set of positive k

numbers such there exists a set {y1,...,yk} S where yi t} i=1

Hint: Note that you have to use exactly k elements of S for this variant of SUBSET-SUM where k is specified by the user.

(3) COMPLETE = {G | G is a complete graph (i.e., it contains a clique of size n where n is the number of nodes in the graph)}

(4) SPATH = {G,s,t,k | G is an undirected graph with a simple path from s to t with length at most k}

Hint: A simple path has no repeated nodes. Do a search similar to the one we did for P AT H but also keep track of the path length required required to reach each node

Explanation / Answer

4.
For SPATH = {<G,s,t,k> | G is an undirected graph with a simple path from s to t with length at most k}

The marking algorithm for recognizing PATH can be modified to keep track of
the length of the shortest paths discovered. Here is a detailed description of the
algorithm.
“On input <G, s, t, k> where m-node graph G has nodes a and b:
   - Place a mark “0” on node s.
   - For each i from 0 to m:
   - If an edge (a, b) is found connecting a marked “i” to an
   unmarked node b, mark node t with “i + 1”.
   - If t is marked with a value of at most k, accept. Otherwise, reject

Related Questions

Navigate

• Browse (All)
• Browse 2
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.