COSC1107/1105 Computing Theory
School of Computing Technologies Semester 2, 2021
Tutorial No. 11: Computational Complexity and Computability
PART 1: Computational Complexity…………………………………………………………….. (a) State what it means for a problem to be in P, NP, NP-COMPLETE, and NP-HARD.
Solution:
• A problem is in complexity class P iff there exists a deterministic TM that solves it and whose running time is polynomial.
• A problem is in complexity class NP iff there exists a non-deterministic TM that solves it and whose running time is polynomial.
• A problem is in complexity class NP-COMPLETE iff it is in NP and every problem in NP can be reduced to it via a computable function in polynomial time.
• A problem is in complexity class NP-HARD iff all NP problems can be reduced to it via a function com- putable in polynomial time.
(b) Let A and B be problems such that A can be reduced to B in polynomial time. What can you conclude from this if i. A∈NP
ii. B∈NP
iii. A is undecidable
Solution: From this we conclude that B is also undecidable.
iv. B is undecidable
Solution: We cannot conclude anything from this.
v. AisNP-complete
vi. BisNP-complete
(c) , a student of CT in 2014, has been able to build a Python program that solves the boolean satisfiability problem. Her program has a complexity of O(n8 + n). Explain precisely why Anna is now famous and rich.
Solution:
Solution: If A is NP-complete (and not just in NP) then this would show that B is NP-hard. But we need to know that A is NP-complete, not just in NP.
Solution: We cannot conclude anything from this. We would need to know more about A, such as whether it is N P -complete or not.
Solution: From this we conclude that B is N P -hard. We would also need to know if B is in N P before we can conclude that B is also N P -complete.
Solution: We cannot conclude anything from this. If A is in N P , this is just an example of a reduction to B that we know must exist for all problems in N P .
1
COSC1107/1105 – Computing ThTeuotroyrial 7: Computational Complexity and Computability Page 2 of 2
has found a polynomial deterministic TM (Python is deterministic) for solving the SAT problem, which has been shown by Cook to be in NP-COMPLETE. Hence, because any problem in NP can be reduced in polyno- mial time to SAT (as SAT is NP-HARD) we can use Anna’s solution to solve any problem in NP in deterministic polynomial time. Hence every problem in NP can now be solved in deterministic polynomial time and hence every problem in NP is also in P. Hence, NP = P and Anna has solved one of the 1 million dollar questions!
(d) Prove that 4-SAT, which is like 3-SAT but where every clause has at most 4 literals, is NP-complete.
Solution:
Proof: In order to prove that 4-SAT is NP-COMPLETE, we must first prove that it is in NP. We can do this by showing that a solution to 4-SAT can be verified in deterministic polynomial time.
An instance of 4-SAT I4 comprises n clauses, each with 4 literals. A solution to 4-SAT, S4, consists of a vector of truth assignments, each corresponding to one of the literals. This vector can be verified by iterating over each clause, substituting the truth value for each literal and evaluating the clause. If all n clauses evaluate to True, then S4 is a valid solution. With n clauses and 4 literals, this verification can be performed with 4n substitutions, clearly polynomial time, so 4-SAT is in NP.
Secondly, we must show that 4-SAT is in NP-HARD. We do this by showing that 3-SAT, a known NP-COMPLETE problem, can be reduced to 4-SAT in deterministic polynomial time. Given an instance of 3-SAT I3, consisting of n clauses, each with 3 literals. We can construct an instance of 4-SAT I4 by taking each clause in I3 and simply du- plicating one of the literals in its I4 counterpart, as a∨a ≡ a. For example, the clause (a∨¬b∨c) → (a∨¬b∨c∨c). We will show that an instance of 3-SAT I3 has a solution iff an instance of 4-SAT I4 constructed in this way has a solution.
• Suppose I3 has a solution S3. Then by our construction, each clause in I4 has exactly the same literals as its counterpart in I3, just one of them is duplicated. So the solution S4 is identical to S3.
• Suppose I4 has a solution S4. Then by our construction, each clause in I3 is identical to its counterpart in I4, except with the duplicated literal removed. Therefore S3 = S4.
Hence, an efficient algorithm that solves 4-SAT will solve 3-SAT, meaning 4-SAT is at least as hard as 3-SAT. Because 3-SAT is known to be NP-HARD, so to must 4-SAT be NP-HARD and as we have already shown 4-SAT to be in NP, 4-SAT must be NP-COMPLETE. QED.
(e) Consider the following two classical problems in Computer Science: • The Set-Cover problem:
– Input: (U,A,k) where A is a set whose members are subsets of U, and k ∈ N.
– Question: Does U have an A cover of size k? (informally, can we “cover” U with k elements of A?)
An A cover of U is a subset B of the set of subsets A such that for every element u ∈ U there exists a set B ∈ B such that u ∈ B (i.e., ∀u ∈ U, ∃b ∈ B such that u ∈ b ∈ B ⊆ A).
• The Vertex-Cover problem:
– Input:(G,K)whereG=(V,E)isagraphandK∈N. – Question: Does G have a vertex cover of size K?
AvertexcoverofG=(V,E)isasubsetWofV suchthatforeveryedge(i,j)∈E,eitheri∈Worj∈W. It is well known that Vertex-cover is an NP-COMPLETE problem. Using that fact, demonstrate that Set-Cover is also in NP-COMPLETE.
Solution:
Proof: In order to prove that the set cover problem is NP-COMPLETE, we must first prove that set cover is in
NP. To do this we will show that given a solution to the set cover problem, a set of sets B; B can be verified in deterministic polynomial time. FirstwemustcheckthatB⊆Aand|B|=k;thenwemustalsocheckthat∀u∈U,u∈b∈Bb. Ifallof these conditions are true, then we accept B, otherwise we reject. As all of these operations can be performed in deterministic polynomial time, the verifier runs in deterministic polynomial time and set cover is in NP.
Finally, we must prove that set cover is in NP-HARD. This is done by showing a known NP-COMPLETE problem, vertex cover, can be reduced to the set cover problem in deterministic polynomial time.
Given an instance of the vertex cover problem, V c = (G, K), where G = (V, E) is a graph and K ∈ N. V c can be turned into an instance of the set cover problem, Sc = (U,A,k) by setting k = K, U = {i | ei ∈ E} (i.e., the
setofedgeindices)andA={Av |Av ={i|ei ∈E,v∈ei},∀v∈V}.(i.e.,Aisasetofsetscontainingthe indices of the edges incident to each vertex).
RMIT CT 2021 (Semester 2) –
COSC1107/1105 – Computing ThTeuotroyrial 7: Computational Complexity and Computability Page 3 of 2
For example, given the following instance of the vertex cover problem Vc = (G,K) where K = 2, we can construct an instance of the set cover problem Sc = (U, A, k) in the following way:
b
c e1
e3
d
⇔ Aa Ab Ac Ad Ae
U K=2 A
= {1,2,3,4,5}
= {Aa, Ab, Ac, Ad, Ae} ={1,2,5}
={1}
={2,4,3}
={3}
={4,5}
a e5 e
k=2
In this example, the solution to the vertex cover problem would be {a, c} and the solution to the set cover problem would be {Aa, Ac}.
We will now show that an instance of the vertex cover problem V c = (G, K ) has a solution iff an instance of the set cover problem Sc = (U, A, k) constructed in this way has a solution.
• Suppose V c has a cover of size K. Let W ⊆ V be this set of nodes that comprise the cover. By our construction, B is a set of subsets of U that each contain the indices of each edge incident to each vertex in W. As |W| = K and k = K, so |B| = k. Finally, since any element u ∈ U corresponds to an element e ∈ E, and W is a cover for G. It must be the case that B is a cover for U as any e ∈ E has at least one end point in W, so B contains at least one of the sets for any u ∈ U.
• Suppose Sc has a cover of size k. Each set in B corresponds to a vertex, so let W ⊆ V be the set of vertices corresponding to B. |B| = k and K = k, so |W| = K. Finally, each element u ∈ U corresponds to an edge e ∈ E. By our construction, each set in B corresponds to an end point of an edge e ∈ E and if B is a cover for U, then W must contain vertices that are the end points for all e ∈ E, and so is a cover for G.
Therefore, if we have an efficient algorithm that can solve Sc, we can use this algorithm to solve V c and hence, set cover is at least as hard as vertex cover. As vertex cover is known to be NP-HARD, so must set cover be in NP-HARD as well.
As we have shown that set cover is both in NP and NP-HARD, it must be NP-COMPLETE. QED.
(NB: This solution is more detailed than you would need to produce in an exam, but it is that way in order to make sure all of the steps are clear and the reasoning is easy to follow. If asked to prove this in an exam, it would be sufficient to show that set cover is in NP, give a reduction (in words, if you like) from vertex cover to set cover and then show, briefly, how a solution to the vertex cover problem would be accepted if and only if a solution to the constructed set cover problem is also accepted. You do not need to go into so much detail, or provide an example – but you can if you like!)
Another solution can be found here. It does not matter if you do not get the exact details but hopefully you can follow it enough to be able to get the idea of the reduction and that it is a polynomial one.
A more detailed proof can be found here and a great pack of slides with visual representations for this and other examples can be found here.
(f) (Advanced; optional)
The decision version of the knapsack problem states: “Given a set of n items, each with a weight {w1 , w2 , . . . , wn }
and a value {v1, v2, . . . , vn}, and two integers, capacity K and a total value V . Is there a subset S ⊆ {1, 2, . . . , n} suchthati∈Ssi ≤Kandi∈Svi ≥V?”
Prove, using problem reduction, that the decision version of the knapsack problem is NP-Complete. Do this by first proving that it is in NP and then give an appropriate reduction from a known NP-Complete problem to show it is in NP-Hard.
Some of the known NP-Complete problems are subset sum, SAT, CNFSAT, etc. You don’t have to do the actual reduction, however, show your reasoning for reduction. You can research about this using the web.
Solution:
Proving that the decision version of the knapsack problem is in NP is easy. We need to show that we can check whether a solution to the problem satisfies the constraints or not, using a Turing machine in polynomial time. Given a solution to the problem S, we can easily check i∈S si ≤ K and i∈S vi ≥ V by just adding the appropriate
RMIT CT 2021 (Semester 2) –
e2
e4
COSC1107/1105 – Computing ThTeuotroyrial 7: Computational Complexity and Computability Page 4 of 2
weights and values and comparing them against K and V .
In order to prove that the decision version of the knapsack problem is NP-Hard, we give a reduction from the well-known NP-Complete problem, subset sum.
The decision version of the subset sum problem states: “Given a set of non-negative integers S = {s1 , s2 , . . . , sn } and an integer T . Is there a subset C ⊆ S such that c∈C c = T ?”
The structure of this problem is very similar to that of the knapsack problem, and that is why we chose it for reduction (problem selection is VERY important when doing reduction proofs!). Where the knapsack problem says that the sum of weights must be at most than K and the sum of values must be at least than V , the subset sum problem says they must be equal to T. The key insight here, is that although the set of weights and values are different, the set of indices is the same for both. So if we construct a version of the knapsack problem such that vi =wi,∀i∈{1,2,…,n}andV =K,theni∈S si =i∈S vi =V =K.
Therefore, if we can efficiently solve the knapsack problem, that will give us a solution to the subset sum problem — a known NP-Hard problem. Hence, the knapsack problem must be NP-Hard as it is at least as hard as the subset sum problem.
As the decision version of the knapsack problem has been shown to be both in NP and NP-Hard, we can say that it is NP-Complete.
RMIT CT 2021 (Semester 2) –
End of tutorial worksheet