The Australian National University Semester 1, 2022 Research School of Computer Science Tutorial 9
Theory of Computation
This tutorial sheet contains way more exercises that you will be able to solve or discuss in the tutorial.
Exercise 1 Properties of Complexity Classes
Copyright By PowCoder代写 加微信 powcoder
Prove that if any NP-complete problem P is also in P, then P = NP.
Solution. Clearly P ⊆ NP, as deterministic TM’s are a subclass of non-deterministic TM’s. So it is
sufficient to show that NP ⊆ P.
Let L be a problem in NP. Then there is a polytime reduction to P (taking p(n) time), as P is NP- complete. But P is in P, and the input to P is bounded above by p(n)+n, so we can solve any instance of a P problem in q(k) time, where k is the size of the instance of the P problem, and q is some polynomial. Then L can be solved in no more time than q(p(n) + n), which is polynomial. Hence L ∈ P. Hence P = NP.
Exercise 2 Boolean Satisfiability Problem
1. Let L be a problem such that SAT ≤P L. What can we say about L? Is it in P? In NP? NP-complete? NP-Hard?
Solution. Since any L2 in NP can be reduced to SAT, and SAT reduces to L, we have that L is NP-Hard. We can’t really make any other claims with the information provided, as there exists problems in NP-Hard that are not in NP.
2. Suppose that L is a problem with the property that L ≤P SAT. What can we say about L? Is it in P? In NP? NP-complete? NP-hard?
Solution. Any L instance can be reduced to a SAT instance, so L must be NP.
It can be that L is in P : for example, the problem L = Σ∗ can be polytime reduced to SAT by the (polytime computable) function f(w) = x, for a variable x. Note that w ∈ Σ∗ ⇐⇒ x is satisfiable, as both the left and the right hand side are trivially true.
If P ̸= NP, then it can also happen that L ∈ NP \P, for example L = SAT itself (which we reduce to SAT using the identity function). This example also shows that L can be NP-complete.
In summary, the only thing that we can say with certainty is that L ∈ N P .
Exercise 3 Variants of CSAT
We recall the following terminology
• a literal is either a variable or a negated variable, e.g. x or ¬x.
• a clause is the disjunction (logical OR) of zero or more literals, e.g. x or x ∨ ¬y or x ∨ ¬y ∨ ¬z.
• a boolean expression is in conjunctive normal form (or CNF) if it is a conjunction (logical AND) of zero or more clauses, e.g. x, x ∨ y, (x ∨ ¬y) ∧ x, (x ∨ y) ∧ (¬x ∨ ¬y). Non-examples include ¬¬x, ¬(x∨y), (x∧y)∨z.
as well as the formulation of the CSAT problem:
(CSAT) Is a given boolean expression in conjunctive normal form (coded as a string) satisfiable?
We have seen in the lectures that CSAT is NP-complete. There are variants of CSAT where the length of the clauses are fixed. We say a boolean expression is k-CNF if it is in CNF, and each clause has exactly k pairwise distinct literals.
For example, 1-CNF expressions include ¬x ∧ y, and z ∧ ¬z. Similarly, 2-CNF expressions include (x ∨ y)∧(¬x∨z), and 3-CNF expressions include (x∨y∨¬x)∧(y∨z∨w), and so on. This gives the k-SAT problem for k ∈ N.
(k-SAT) Is a given boolean expression in k-CNF (coded as a string) satisfiable? 1. Prove that 1SAT is P.
Solution. An instance of a 1SAT problem is just the logical AND of many literals. Each literal needs to be true for the entire expression to be true, so an instance of a 1SAT problem is satisfiable iff it doesn’t contain both any variable and it’s negation. So, for each literal in the expression, scan the entire expression to see if it’s negation is present, and accept iff no literal also has it’s negation present, at a cost of O(n2).
2. Prove that 2SAT is P.
(Hint: p ∨ q ≡ ¬p ⇒ q. Build a directed graph where each node is a literal, and edges represent implications. Use the graph to find valid assignments to variables.)
Solution. Letφ=φ1∧···∧φk bea2SATformulawithkclausesandvariablesx1,…,xn.Each clausel1∨l2 isequivalenttotwoimplications:¬l1 →l2 and¬l2 →l1.ConstructagraphG=(V,E) where
• V = {x1,…,xn,¬x1,…,¬xn}
• E={(l,l′)|l→l′ isequivalenttoaclauseinφ}.
Note that if there is a path, i.e. a chain of implications
l1 →l2 →···→lm
where the li’s are literals, then any valuation π with π |= φ and π |= l1 must satisfy π |= l2, π |= l3, . . . , π |= lm . In this case, we call l1 and lm transitively connected. Note that ¬lm and ¬l1 are transitively connected whenever l1 and lm are transitively connected.
In particular, if li and ¬li are transitively connected, then there is no valuation π with π |= φ and π |= li.
We claim that φ is not satisfiable if and only if for some xi, both xi is transitively connected to ¬xi and ¬xi is transitively connected to xi.
To see this, first assume that both xi is transitively connected to ¬xi and ¬xi is transitively connected to xi.
• if π(xi) = T, then all literals along the chain xi → ··· → ¬xi must have the same truth value (as each implication that is part of the chain needs to be true), whence also ¬xi must be true, contradiction.
• if π(xi) = F, then the same argument applies with the chain ¬xi → ··· → xi.
Now assume that for no xi we have that both xi is transitively connected to ¬xi and ¬xi is
transitively connected to xi. Construct a valuation by picking a variable x.
• if x is not transitively connected to ¬x, put π(x) = T and π(y) = T for all y that are transitively
connected to x, and π(y) = F for all ¬y transitively connected to x.
• if ¬x is not transitively connected to x, put π(x) = F , and π(y) = T if ¬x and y are transitively
connected, and π(y) = F if ¬x and y are transitively connected.
The partial assignment created in this way is consistent, for suppose that x is transitively connected to both y and ¬y. Then ¬y is transitively connected to ¬x, and hence x is transitively connected to ¬x, contradiction. The consistency argument for the second case is similar.
If not all variables have yet been assigned, pick an unassigned variable x′ and repeat. This also creates a consistent assignment, for suppose e.g. both x and z, as well as x′ and ¬z are transi- tively connected. Then z and ¬x′ are transitively connected, and hence x and ¬x′ are transitively connected, i.e. x′ would have been assigned in the first step.
Continue in this way until all variables have been assigned. This gives a consistent assignment π with π |= φ.
To see that π |= φ, pick a clause l∨l′ in φ. Then one of the implications ¬l1 → l2 or ¬l2 → l1 has been visited in the construction of π as all variables have been assigned, and therefore either π|=¬l1 →l2 orπ|=¬l2 →l1,henceπ|=l1∨l2.
In summary, we have shown that φ is satisfiable, if it is not the case that both x and ¬x, as well as ¬x and x are transitively connected. To check that φ is satisfiable, we can therefore iterate througn all variables x1, . . . , xn and check whether both xi and ¬xi, as well as ¬xi and xi are transitively connected. If this is the case for some variable, return ’not satisfiable’, otherwise return ’satisfiable’. The latter algorithm can be implemented in polynomial time.
3. let l1, . . . , l5 be literals, and y1, y2 variables that does not occur in any of the li’s. Show that every variable assignment that makes l1 ∨ · · · ∨ l5 true can be extended to a variable assignment that makes
(l1 ∨l2 ∨y1)∧(l3 ∨¬y1 ∨y2)∧(l3 ∨l4 ∨¬y2)
true. Conversely, show that every variable assignment that makes (l1 ∨ l2 ∨ y1)(l3 ∨ ¬y1 ∨ y2)(l3 ∨
l4 ∨¬y2) true also makes l1 ∨···∨l4 true.
(Hint: You can think of the intermediate term ¬y1 ∨ y2 equivalently as an implication y1 ⇒ y2. )
Solution. Assume x1 ∨ x2 ∨ x3 ∨ x4 is satisfiable. Then there exists i such that xi can be assigned true without violating any of the hidden constraints, as if not, then x1 ∨ x2 ∨ x3 ∨ x4 wouldn’t be satisfiable.
Ifi=1ori=2,thenbychoosingy1 =F,then(x1∨x2∨y1)istrue(asoneofthex’sistrue) and (x3 ∨x4 ∨¬y1) is true (as y1 is false), hence (x1 ∨x2 ∨y1)(x3 ∨x4 ∨¬y1) is true under some assignment, and therefore satisfiable.
Assume (x1 ∨ x2 ∨ y1)(x3 ∨ x4 ∨ ¬y1) is satisfiable. Suppose all the xi’s were forced by the hidden conditions to be false. Then the above is logically equivalent to y1 ∧ ¬y1, which is unsatisfiable, a contradiction. Hence at least one of the xi’s can be true without breaking the hidden conditions, and thus x1 ∨ x2 ∨ x3 ∨ x4 is satisfiable.
4. Why can’t we prove 3SAT is P in the same fashion as for 2SAT?
Solution. As p ∨ q ∨ r ≡ ¬p ⇒ (q ∨ r), but forcing ¬p to be true doesn’t indicate which of q or r
is true. In the worst case for n many clauses, we might have exponentially many guesses to make.
Exercise 4 Reductions to 3SAT
3SAT is one of the simplest NP-complete problems for the purposes of polytime reductions, so it’s very useful for proving that other problems are NP-complete.
1. Prove that kSAT for k ≥ 3 is NP-complete. Hint. Reduce from 3SAT using previous exercise.
Solution. Proof by induction. Trivial for k = 3. Assume that for some k that 3SAT instances can be reduced to kSAT in polytime. Prove for (k+1)SAT. Take a 3SAT instance, and polytime convert to a kSAT instance. Then, take any clause of the form x1 ∨ … ∨ xk, and rewrite as (x1 ∨ … ∨ xk ∨ z)(x1 ∨ . . . ∨ xk ∨ ¬z), which preserves satisfiability (by an argument identical to the previous exercise), and is a product of clauses of length k + 1. Repeat this rewriting rule for each of the clauses. It’s clear this rewriting rule will take polytime, as the new clause is proportional in size to the old clause. The composition of two polytime reductions is polytime, hence we can reduce 3SAT to (k + 1)SAT in polytime.
All that is left to show is that kSAT is NP, which is immediate as kSAT is a special case of SAT, and SAT is NP.
2. The linear integer programming problem (LIPP) is defined as the decision problem that given a set of integer variables x1 , . . . , xn , and a collection of inequalities of the form ni=1 ai xn ≥ c or ni=1 aixn ≤ c for some integer constants a1, . . . an, c, does these exist an assignment of the variables xi that satisfies all of the inequalities?
Show that LIPP is NP-Hard. (Hint: Take a 3SAT instance, and work how how to change each of the clauses into a set of inequalities such that the inequalities have a integer solution iff the clause is satisfiable.)
Solution. Take a 3SAT instance with variables x1, . . . , xn. Add the inequalities xi ≥ 0 and xi ≤ 1 for all i (Which forces each variable to be either zero or one). Take a 3SAT expression. We will develop an inequality for each clause, such that the inequality has solutions iff the clause is satisfiable. Hence, the entire boolean equation (being the product of many clauses) will be satisfiable iff all of the inequalities are satisfied. Represent positive literals x as x, and negative literals ¬x as 1 − x. We can then represent 3SAT clauses by applying the above transformation to each literal, for example x ∨ ¬y ∨ z becomes x + (1 − y) + z ≥ 1. Since each variable is either 0 or 1, 1 − x acts like negation (turning 0’s into 1’s and vice versa, and of any of the variables is 1, the sum is greater than or equal to one, so there will be an assignment of the variables that names the sum greater than or equal to 1 iff the original clause was satisfiable.
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com