The Australian National University Research School of Computer Science
Theory of Computation
Release Date. Monday, May 18, 2020
Due Date. Monday, June 1, 2020, 23.50 Canberra time Maximum credit. 50
Copyright By PowCoder代写 加微信 powcoder
Exercise 1 Pessimistic Sat
Semester 1, 2020 Assignment 3 of 3
A literal in a clause is negative if it is of the form ¬x for a variable x, and positive (that is, a non-negated variable) otherwise. For example, in the clause ¬x ∨ ¬y ∨ z, the literals ¬x and ¬y are negative, and the literal z is positive.
We call a clause pessimistic if it contains at most one positive literal. For example, the clauses ¬x∨¬y∨z and ¬x ∨ ¬y as well as the (one-element) clauses x and ¬y are pessimistic.
Consider the following variant PESSIMISTIC SAT of the CSAT problem: Input: A formula F that is a conjunction of pessimistic clauses.
Problem: Is F satisfiable?
Prove that PESSIMISTIC SAT is in P.
(20 credits)
Solution of Exercise 1
Firstly, if a instance of PESSIMISTIC SAT never contains any clauses of length one, then it is always satisfiable, and the answer is yes.
Reason being, that every clause must contain at least one negative literal, so by assigning every variable to false, every clause contains at least one literal that is set to true, so all the clauses evaluate to true, and the entire expression is satisfied.
If not, scan through the expression to find a clause of length 1 (i.e. a literal) If that clause is a positive literal (i.e of the form xi) then the corresponding variable xi being set to true is a necessary condition for satisfiability. Delete the clause xi (as y ∧ T rue = y) and remove any clauses that contain xi (as by setting it to true, we have that y ∨ T rue = T rue, so it’s redundant to keep the xi.) Also, for any clause containing a ¬xi term, remove that term, (as y ∨ F alse = y). The exception is when one of the clauses is ¬xi itself, as if xi must be true, then ¬xi must be false and this clause is unsatisfiable. So we reject and the answer is no.
If that clause is a negative literal (i.e of the form ¬xi), then we repeat the above argument, removing the clause ¬xi, removing any clauses that contain ¬xi, and modifying any clauses that contain xi so they no longer do so. If any of the clauses is exactly of the form xi, then it is unsatisfiable, and we reject.
Repeat the above until we reach a contradiction and reject (by having two clauses of the form xi and ¬xi, or all the clauses are length two or greater, in which case we accept, or there are no more clauses left, having deleted them all (as in the case for x ∧ (x ∨ y), in which case we accept. We must reach one of these cases, as in each stage we only eliminate clauses of length one, and then trim down the size of other clauses, so the expression gets strictly shorter at each stage.
It takes linear time to compute one pass of this algorithm (as we pass through the expression and eliminate terms that match the one we are looking for) and we remove at least one term each pass, leading to a worst case complexity of O(n2).
Exercise 2 NP-Hard but not in NP (15 credits) Recall that a problem A is NP-hard if every problem in NP is polytime reducible to A.
Give an example of a problem A such that A is NP-hard, but A itself is not in NP. Give proof for both claims.
Solution of Exercise 2
We choose A to be the halting problem. Clearly A is not in NP, as if it were, then A could be decided by a deterministic Turing machine that explores all possible paths the non-determinstiic machine would take (likely taking exponential time), which means that A will be decidable, a contradiction.
Now, take any NP problem L. Then there must exist a deterministic Turing machine M such that for any input x ∈ L, there exists a certificate c such that M(x,c) halts in polynomial time p(|x|) and accepts.
Now, we devise an algorithm Ω as follows. Ω takes an encoding of two inputs, a string x and a description of a verifier M. It decodes x and M, and then and tries all |Γ|p(|x|) possible certificates c (where Γ is the tape alphabet) emulating M(x,c), and if any of the emulations accepted, then Ω accepts.
If non of the emulations accepted, then Ω runs in an infinite loop.
Clearly, x ∈ L iff Ω(x,M) halts. We can then feed a description of Ω and it’s input (x,M) to the
halting oracle A, which will tell us if Ω(x,M) halts or not, and thus if x is in L or not.
Last, this transformation is polynomial time, as we can write down the description of Ω once, and the transformation is to merely encode Ω together with it’s inputs x and M to make it an instance of the halting problem. Encoding the machine is already done, and encoding the machine Ω together with it’s input in a prefix-free manner as one string is polynomial time. (Consider the encoding 1|x|x⟨Ω⟩, for instance, where ⟨·⟩ is the function encoding turing machines as binary strings.
Exercise 3 Jailbreak! (15 credits)
Prisoners at a jail are trying to organise an escape plan. The plan will succeed only if there is a large enough group of conspiring prisoners. More precisely, the plan succeeds if there is a group of prisoners of size at least k such that any two prisoners in this group trust one another.
Consider the decision problem JAILBREAK:
Input: An undirected graph whose vertices represent prisoners, and where an edge between two vertices
(prisoners) signifies that the two vertices (prisoners) trust one another, and a natural number k ≥ 0. Problem: Does there exists a set of prisoners (vertices) of size ≥ k such that any two prisoners (vertices)
in that group trust one another (are connected by an edge)? Prove that JAILBREAK is NP-complete.
Solution of Exercise 3
First, note that JAILBREAK is NP, as given a solution (a set of prisoners of size s ≥ k that all trust each other), we can verify this in s2 time, by just checking each pair of prisoners in the group against the original graph, and make sure that they share an edge. This is bounded above by O(n2) time, where n is the size of the input.
Now, we need to show that JAILBREAK is NP-Hard. We want to reduce from another NP-Hard problem, the canonical solution is to reduce either from 3SAT, or from IS (Independent Set). I’ll go through both solutions.
Let F = C1 ∧C2 ∧…∧Cm be an instance of 3SAT, where each clause Ci is of the form Ci = yi,1 ∨ yi,2 ∨ yi,3, and each yi,j is a literal (that is, either xk or ¬xk, where xk is a variable.) We
polytime reduce 3SAT to JAILBREAK by setting the number of prisoners require to escape, k, to be equal to the number of clauses m, and constructing the following graph G = (V, E), where
V ={yi,j :1≤i≤m,1≤j ≤3}
E = {(yi,j,yk,l) : 1 ≤ i,k ≤ m,1 ≤ j,l ≤ 3,i ̸= k,yi,k ̸= ¬yk,l}.
That is, we make 3m vertices for every literal in every clause, and we add an edge between two vertices if
• They represent literals from different clauses, and
• The literals they represent do not contradict each other (don’t connect a literal to it’s negation)
For example, here is the corresponding graph for
(¬x ∨ y ∨ z) ∧ (x ∨ y ∨ z) ∧ (¬x ∨ ¬y ∨ ¬z)
where the vertices are labelled with the literals they represent, for clarity. Here, I’ve highlighted a satisfying assignment x = F,y = T,z = T and (one possible) corresponding jailbreak group that it forms.
Now, suppose that F was satisfiable. Then there is a assignment of variables such that each clause has at least one literal evaluate to true. Let S = {l1, l2, . . . lm}. Now, any two literals in S share an edge, as they are from different clauses, and cannot possibly contradict each other (as otherwise the assignment couldn’t make them both true). Then S forms a complete subgraph of G with m vertices, which for the JAILBREAK problem represents m many prisoners that all trust each other, and can successfully work together to escape.
Conversely, suppose that the boolean formula was not satisfiable. We assume for a contradiction that the corresponding graph G constructed from F is a valid instance of JAILBREAK. Then there exists a complete subgraph S with m vertices. Now, each vertex represents a literal in a clause in F .
No two vertices in S can represent literals in the same clause in F, as if two literals were from the same clause, an edge would not have been placed between them.
So, for every vertex in S, take the literal that it corresponds to, and if it is a negative literal (e.g ¬x), then assign the underlying variable (x) to false. Otherwise, if it is a positive literal (x) then set the underlying variable (x) to true. This assignment doesn’t cause any contradictions, as S doesn’t contain both some literal and it’s negation, as they don’t share edges in the graph. Since we have m vertices in S, and no two verticies originate from literals in the same clause in F, we must have each vertex represent a literal in each of the m different clauses. So the assignment means that at least one literal in each clause is true, which means that formula is satisfiable, a contradiction.
Independent Set (IS)
Let graph G and number k be an instance of IS. Then we polytime transform G = (V,E) to Gc := (V, E′), the compliment graph, defined as the same vertices, but Gc has an edge between two vertices u and v iff G does not have an edge between u and v.
This reduction is polytime, as for each pair of vertices (O(|V |2) many), we check if they have an edge connecting then in the original graph (via scanning through all edges at a cost of at most O(|E|), for a total cost bounded above by O(n3), where n is the size of the input.
Now, suppose G has an independent set of size k. Then we have a subset of the graph S where for any two different vertices in S, they do not share an edge. Then for the compliment graph, any two different vertices in S do share an edge, which represents a group of prisoners of size k that all trust each other.
Conversely, if G isn’t a valid instance of the independant set problem, then for any set of k vertices in G, there are two different vertices u and v that share an edge. When we take the compliment graph, then for any set of k vertices in Gc, there are two different vertices u and v that do not share an edge, corresponding to any potential jailbreak crew having at least two members who distrust each other, and the jailbreak will fail.
Rubric. We expect a level of detail comparable to that of the model answers of the tutorial exercises.
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com