CS 21 Decidability and Tractability Winter 2024
Posted: March 13
Final Exam Solutions
If you have not yet turned in the Final you should not consult these solutions.
Copyright By PowCoder代写 加微信 powcoder
First, the problem is in PSPACE, for the usual reason for 2-player games. We give a simple recursive algorithm for a slightly more general problem, in which the target value is not necessarily zero, but a specified integer B.
Initially, the problem instance is given by (G,s,B = −f(s)). We will use the notation f(v) to denote the integer labeling node v.
Our recursive algorithm answers YES or NO to whether or not there is a win for Player 1 and it operates as follows. If there exists an edge (s,v) where v is a sink, and B = f(v), then there is clearly a win for Player 1 by taking this edge, and we return “YES.” Otherwise, we consider all sequences of two moves, one by Player 1 and one by Player 2. In other words we consider all paths starting from s, consisting of 2 directed edges (s,v) and (v,u). For each such path we (recursively) ask whether there is a win for Player1withtheprobleminstance(G,u,B′),whereB′ =B−f(v)−f(u). Ifuitselfis a sink, then the answer is YES if B′ = 0 and NO otherwise; if u is not a sink then the anwer is the result of the recursive call asking if there is a win for Player 1 with problem instance (G,u,B′). After recording the results of these queries, if there exists a v (with an edge (s, v)) such that for all u (with an edge (v, u)) the answer is YES, then we have determined that there is a win for Player 1 in the original instance. If not, then there is no win for Player 1 in the original instance.
This recursive algorithm has recursion depth no larger than the number of vertices of the graph (because it is acyclic), and the state we need to remember at each level is just the running sum, the target sum, and which path of length two we are currently examining (all of which require at most polynomially many bits in the size of the input). Thus the total space usage is polynomial in the size of the input, as required.
We reduce from qsat and we refer to the reduction for subset sum from Lecture 22. An instance of qsat is a 3-CNF formula φ(x1,x2,…,xn), with m clauses, and we are asking whether
∃x1∀x2∃x3∀x4 ···Qxnφ(x1,x2,…,xn) = 1.
We assume without loss of generality that n is even (we can add a dummy variable if
necessary). We now describe the reduction.
Recall that s is the start node of the graph, and we set f(s) = 0. There are two
directed edges from s = s to the nodes u ,v respectively, and we set f(u ) = xtrue 11111
and f(v1) = xfalse from the subset sum reduction applied to φ. We then have a single 1
directed edge from u1 to a node w1 with f(w1) = 0, an edge from v1 to w1, and a directed
edge from w1 to t1 with f(t1) = 0. From t1 we have an identical structure with the two
neighbors of t being u ,v and f(u ) = xtrue and f(v ) = xfalse from the subset sum 1222222
reduction applied to φ. And so on, with each of the n variables in φ corresponding to a “layer” with depth 3. The directed graph has exactly the same structure as the intial part of the generalized geography reduction (up to the “clause gadget”), and the node labels are all zero except for f(ui) = xtrue and f(vi) = xfalse.
Now, we have three outgoing edges from tn to nodes with values 0, FILL11 and 2FILL11
(again referring to the subset sum reduction applied to φ). There are then directed edges to an intermediate node labeled with 0, and then again three outgoing edges to nodes with values 0, FILL12 and 2FILL12. And we continue in this fashion to create m additional “layers” of the directed graph each with depth 2, using FILL1i and 2FILL1i
in layer i. Finally, the last node (which has incoming edges from the nodes labeled with values 0, FILL1m and 2FILL1m, and no outgoing edges) is labeled with the value −B (again referring to the subset sum reduction applied to φ).
This layered graph is set up in such a way that the two players playing the game starting from s must alternate in selecting one of xtrue and xfalse to add to the sum for i =
1, 2, . . . n, and then player 1 is able to add 0, 1, or 2 multiples of FILL1i in sequence for
i = 1,2,…,m (and player 2 is always forced to add zero in this phase).
Clearly this reduction runs in polynomial time because we build up a polynomially large graph layer by layer corresponding in a simple way to the n variables and m clauses of φ.
We argue that YES maps to YES. In the two-player game interpretation of QSAT (in which the players alternately assign truth values to the variables x1, x2, . . . , xn with player 1 trying to end with a satisfying assignment), a YES instance φ implies that there is a win for player 1. In our game graph G, the first n layers exactly correspond to the players alternately choosing truth values for x1, x2, . . . , xn, and so there is a strategy for player one that ends this part of the game with a satisfying truth assignment selected. Now, in the subsequent 2m layers, player 1 is able to pick the required “filler” values (a 0, 1, or 2 in the required digit) for each of the m clauses, one at a time, to make the sum so far exactly B (player 2 always gets edges leading to nodes labeled with zeros, so he can’t influence the sum in this phase). In the last layer, player 2 is forced to pick −B, and thus there is a win for player 1, since the total is zero.
Now we argue that NO maps to NO. As above, in the first n layers of graph G, the players have alternately selected truth values for x1, x2, . . . , xn, and since φ is a NO instance, player 2 will be able to ensure that the resulting assignment is not a satisfying one. In particular there will be some clause whose corresponding digit has 0 in the sum so far (since all of its literals are false under the selected assignment), which means that no matter what values player 1 selects in the second phase the sum of B will not be reached in the second to last turn, and since −B is selected in the last move, the sum will not be zero. Thus there is not a win for player 1.
2. The language is context free but not regular.
First we argue that it is context free by describing a NPDA deciding it. The NPDA operates as follows: first it pushes a $ onto the stack to mark the bottom of the stack, as usual. The idea is for the stack to contain either k ≥ 0 a’s which indicate that at this point in processing the string, k more a’s than b’s have been encountered, or k ≥ 0 b’s which indicate that at this point in processing the string, k more b’s than a’s have been encountered. To accomplish this, we have the following transitions, each of which is a self-loop to single “main” state:
• when reading an a, with b at the top of the stack, pop the b
• whenreadingana,with$oraatthetopofthestack,pushana • when reading a b, with a at the top of the stack, pop the a
• whenreadingab,with$orbatthetopofthestack,pushab
• when reading a c, do nothing to the stack.
It is clear that each of these rules maintains a stack satisfying the invariant above. Finally, we have rules for when the end of the string is reached. These allow reading an ε with an a or a b at the top of the stack, and transitioning to an “accept” state (i.e., we can accept if we reach the end of the string and there is a non-zero excess of a’s over b’s, or a non-zero excess of b’s over a’s). No other transitions to the “accept” state are available so that in all other situations (namely if there is a $ at the top of the stack), it is impossible to reach the accept state after processing the entire input string.
Now we prove L is not regular, using the pumping lemma for regular languages. Assume for the purpose of contradiction that L is regular. Let p be the pumping length, and consider the string
w = apbp+p!.
Consider any way of writing w as xyz with |y| > 0 and |xy| ≤ p. The second condition implies
that y must contain only a’s. Let k = |y|. We have xyiz = ap−iakibp+p!
Since 1 ≤ k ≤ p, it divides p!. So we can choose i = p!/k + 1 to obtain the string ap+p!bp+p!. This is not in the language, a contradiction. So L cannot have been regular.
Let A = (Q,Σ,δ,s,F) be a DFA deciding language L. Let k be the length of w = w1w2 . . . wk. We construct a NFA B deciding L−w. Machine B will consist of k + 1 copies of A. The first and last copies will have all the transitions of A; the others will have no transitions within the states in that copy. B’s start state will be the start state of the first copy of A, and its accept states will be the accept states of the k-th copy of A. For every transition in A from state p to state q labeled with w1, we add an ε-transition fromstatepinthefirstcopyofAtothecopyofstateqinthesecondcopyofA. In general, for every transition in the A from state p to state q labeled with wi, we add an ε-transition from state p (in copy i) to state q (in copy i + 1).
For a string xw1w2 . . . wkz ∈ L, we can follow the arcs the machine A would have followed while reading x in the first copy of A, then follow the newly available ε-transition to the second copy of A (placing us in a copy of the state we would have been in after reading w1), then the newly available ε-transition to the third copy of A (placing us in a copy of the state we would have been in after further reading w2), and so on. Finally we arrive at the (k + 1)-st copy of A, in the state we would have been in after reading w1w2 . . . wk. Now we proceed in this copy, reading z, which leads to an accept state, since xw1w2 …wkz ∈ L.
If a string is accepted by machine B, then there must be a computation path from the start state in the first copy of A to an accept state in the final copy of A. Let x be the portion of the string read before departing the first copy of A, and let z be the portion of the string read after entering the last copy of A. Then by construction xw1w2 . . . wkz must have been accepted by A, which completes the proof that B satisfies the requirements.
Let M be a Turing Machine that recognizes language L. We describe a Turing Machine N that recognizes L−w. The input to N is a string y of length n, and we must accept iff there is some way to “insert” w into y obtaining a string in L. More precisely, we must accept
iff there exists x,z for which xz = y and xwz ∈ L. There are n+1 possible ways to split y into two strings x,z and insert w, and we simulate M in parallel on each such string. Specifically, for i = 0,1,…,n, we define the string si = y1,y2,…,yiwyi+1,yi+2,…,yn, and we simulate M on the various si in parallel – meaning that we simulate 1 step of M on each si, then the second step of M on each si, then the third step, etc… We halt and accept if any of the simulations accepts.
4. By the Time Hierarchy Theorem there are languages decidable in time O((2n)3k) = O(n3k) that cannot be decided in time O(nk). Picking k = 4, we have a language in P that is not decidable in O(n4) time. Such a language is an example of a language in NP that cannot be decided in time O(n4) regardless of whether or not there is an NP-complete language that can be decided in time O(n2).
It is correct reasoning that the “problem” with the assertion is that reductions can run in time much larger than O(n4), but this is not a proof that there is a language in NP that is not decidable in time O(n4). Deciding a language by applying a reduction to an NP- complete language and the solving the NP-complete language is only one way of deciding it. To really prove that there is no O(n4) algorithm, one needs the Time Hierarchy Theorem (or an equivalent diagonalization argument).
This problem is NP-complete. It is in NP for the usual reasons (given a subset of vertices, we can check in polynomial time whether it has size at least k and whether it is an independent set in G). To show it is NP-hard, we reduce from (3,3)-SAT (from Problem Set 5). We use the reduction from 3-SAT from Lecture 20, but since our starting CNF formula has no variable occurring more than 3 times, the degree of the resulting graph will be at most 4. This is because after placing triangles for each of clauses (or a pair of parallel edges for clauses with two literals and a single node for clauses with a single literal), every vertex has degree at most 2. Then considering each variable xi, its at most three occurrences may require up to two additional edges incident to a node labeled with xi or ¬xi, in the part of the reduction where we add edges between pairs of contradictory literals. The reduction is the same as before, so it runs in polynomial time, and it remains true that YES maps to YES and NO maps to NO.
This problem is in P. Notice that a graph with maximum degree at most 2 is just a disjoint collection of paths, cycles, and isolated vertices. Thus there is a Hamilton path from s to t iff all of the nodes lie on the (unique) path from s to t. Thus to solve the problem in P, we can just perform a DFS from node s, see if we reach t and keep a count of how many nodes we encounter, accepting iff we encounter all of the nodes and reach t.
(c) hitting set-2 is NP-complete. It is clearly in NP because given a purported hitting set H ⊆ U it is easy to check in polynomial time that |H| ≤ k and that each Si has non-empty intersection with H.
To show it is NP-hard, we reduce from vertex cover. Given an instance of vertex cover ⟨G = (V,E),k⟩, we produce the following instance of hitting set-2: U is the set of vertices V, and we have a set S(u,v) = {u,v} in our collection C for each edge (u, v) ∈ E. Note that as required, all of the sets in C have size at most two. We set the
bound k in the instance of hitting set-2 to be the same k as in the instance of vertex cover.
Now, suppose there is a vertex cover V ′ ⊆ V of size at most k. Then we claim that H=V′ isahittingset,sinceforeachsetS(u,v) ∈C,oneorbothofu,vmustbeinV′ and hence in H.
In the other direction, suppose there is a hitting set H ⊆ U of size at most k. By definition, for each edge (u,v), H must include one or both of u,v since it hits set S(u,v) ∈C. ThusV′ =H isavertexcoverofsizeatmostk.
We conclude that hitting set-2 is NP-complete.
(d) This problem is in P. For each way of selecting 75 or more of the first 100 clauses (which is a large constant number), we produce the 2-SAT instance with those clauses together with all of the other clauses. We can solve this 2-SAT instance in polynomial time, since 2-SAT is in P. If any of these at most 2100 instances is a YES instance, then our instance is a YES instance; if all are NO instances, then our instance is a NO instance. The overall running time is at most 2100 times a polynomial, which remains a polynomial.
(e) This problem is NP-complete. It is in NP for the usual reason: given a truth assignment, we can check in polynomial time exactly which clauses it satisfies (and then check that all of the first 100 clauses are satisfied together with at least 3/4 of the other clauses). The reduction is from max-2-sat. Given an instance (φ,k) of max-2-sat we add 100 trivially satisfiable clauses (xi ∨ ¬xi) on fresh variables, and we make these the first 100 clauses. We note that the reduction from Problem Set 5 showing that max-2-sat is NP-complete produces instances with 10m clauses and k = 7m, for an integer m. If we add t additional trivially satisfiable clauses on fresh variables, then we have (among the clauses other than the first 100) a total of 10m + t clauses, of which 7m + t can be simultaneously satisfied iff the max-2-sat instance was a YES instance. Thus choosing t = 2m, we find that 9m = (3/4) · 12m out of 12m clauses are simultaneously satisfiable iff the max-2-sat instance was a YES instance.
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com