TOC Chapter 12

Chapter 12. Time and Space Complexity

In the earlier chapters, we considered the Turing machine (TM) and its acceptance power. By Church–Turing hypothesis, we realize that whatever could be done by a computer can be achieved by a TM. Also, while considering the variations of TMs, we found that even though all of them have the same accepting power, the number of steps could be very much increased in some cases. We also noted earlier that a procedure corresponds to a TM and an algorithm corresponds to a TM, which halts on all inputs. When we study algorithms for problems, we are also interested in finding efficient algorithms. Hence, it becomes essential to study the time and tape (space) complexity of TMs. In this chapter, we study some of these results.

12.1. The RAM Model

The standard model of computation which will represent the action of a modern computer is the family of random access machines (RAM). They are also referred to as register machines sometimes. There are several variations of this model. We consider the following model. It consists of a central processor and an unbounded number of registers. The processor carries out instructions from a given limited set on these registers. Each register can store an arbitrarily large integer. The program is not stored in these registers. It immediately follows that a RAM program cannot modify itself. In this way, it is different from the stored program concept. Also, at any time, the RAM program can refer to only a fixed number of registers, even though it has unbounded number of registers. When the machine starts, the input data is stored in a few registers. When it stops, the result of the computation is stored in a few registers. Let us consider the simplest RAM model which uses only four instructions, viz, increment, decrement, jump on zero, and halt. To add two numbers stored in R₁ and R₂ and store the result in R₁, the following program can be executed.

loop:	Jump on zero, R2, done Decrement R2 Increment R1 done: Halt.

12.2. Time and Tape Complexity of Turing Machines

Space Complexity

Consider the offline TM M. It has a read-only input tape and the input is placed within end markers # and $. It has k storage tapes infinite in one direction. If for every input word of length n, M scans at most S(n) cells on any storage tape, then M is said to be an S(n) space bounded TM, or of space complexity S(n). The language recognized by M, is also said to be of space complexity S(n). It should be noted that symbols on the input tape cannot be rewritten and only the cells used in storage tapes count towards space complexity. This way of looking at the TM helps to consider space bounds less than O(n). For example, log n. If the symbols on the input tape can be written, then minimum space complexity will be n, as we need to look at whole of the input.

Figure 12.1. Multi-tape TM with read only input tape

Problems and Solutions

1.	Show that DT(22n+2n) properly includes DT(22n).
Solution.	By result 2 mentioned in “Some Results on Complexity Classes,” DT(22n+2n) properly includes DT(22n).
2.	What is the relationship between: DS(n2) and DS(n3)? DT(2n) and DT(3n)? NS(2n) and DS(5n)?
Solution.	a. By result 1 mentioned in “Some Results on Complexity Classes,” DS(n3) properly includes DS(n2). b. By result 2 DT(2n) is properly included in DT(3n). c. (c) NS(2n) is included in DS((2n)2) = DS(4n) (result 4) DS(4n) is properly included in DS(5n) (result 1) Therefore, NS(2n) is properly included in DS(5n).
3.	Show that the following problem is NP-complete. One-in-Three-3SAT (1in3SAT) has the same description as 3SAT, except that a satisfying truth assignment must set exactly one literal to true in each clause.
Solution.	One-in-Three-3SAT (1in3SAT) Is the given Boolean expression, given in 3SAT, satisfiable with the additional condition that the truth assignment must set exactly one literal to true in each clause. 1in3SAT is in NP, as we can non-deterministically give a truth assignment and evaluate the expression and also check the additional condition on truth assignment in polynomial time. We next reduce 3SAT to 1in3SAT. Let w0 be a Boolean expression in 3SAT form. From this, construct a Boolean expression for the 1in3SAT problem as follows. To each clause Equation 12.6 of w0 introduce new variables a, b, c, d and convert this to: Equation 12.7 If Equation (12.6) is not satisfiable x1 = x2 = x3 = 0. In this case, looking at Equation (12.7) as lin3SAT problem . Hence, a = b = c = d = 0. Since x2 = 0. (b + x2 + c) becomes 0. Equation (12.7) is not satisfiable or in otherwords, if Equation (12.7) is satisfiable, Equation (12.6) is satisfiable. To prove the other way round, let Equation (12.6) be satisfiable. If x2 = 1, then make b = 0 = c, a = x1, d = x3. Then, Equation (12.7) satisfies the additional restriction and is satisfiable. If x2 = 0, then if x1 = x3 = 1 make a = 1, b = 0, c = 1, d = 0. If x1 = 1, x2 = 0, x3 = 0 make a = 0, b = 1, c = 0, d = 0. If x1 = 0, x2 = 0, x3 = 1 make a = 0, b = 0, c = 1, d = 0. In all cases if Equation (12.6) is satisfiable Equation (12.7) is satisfiable. If w0 has k clauses and n variables, ’ has 3k clauses and n + 4k variables. w0 can be converted to ’ in polynomial time. Hence, the known NP-complete problem 3SAT is polynomial-time reducible to 1in3SAT problem. Hence, 1in3SAT is NP-complete.
4.	Positive 1in3SAT problem is the 1in3SAT problem, where none of the literals are negated. Show that it is NP-complete.
Solution.	Positive 3SAT problem is: Given a Boolean expression in 3SAT form, where none of the literals are negated, is the expression satisfiable? This is a trivial problem as the assignment giving values 1 to all the variables makes the expression satisfiable. It is straightforward to see that positive 1in3SAT problem is in NP. It can be shown to be NP-complete by reducing the 1in3SAT problem to it. Let w0 = c1... ck be a Boolean expression in 3SAT form. From this, we construct an expression w in 3SAT form where none of the literals are negated such that w0 is satisfiable with the 1in3 condition if and only if w is satisfiable with the 1in3 condition. Also, given w0, w can be constructed in polynomial time. Let x1, ..., xn be the variables used in w0. There are k clauses in w0. In w, we use variables x1, ..., xn and also variables y1, ..., yn and z1, ..., zk, z′1, ..., z′k, z″1, ..., z″k. We shall now give the method of constructing w from w0. For each clause ci in w0 some clauses c′i are constructed. If ci is of the form (xk + xl + xm) with no literal negated, this is kept as it is in c′i If ci is of the form (¬xk + xl + xm) with one literal negated, c′i consists of (yk + xl + xm)(yk + xk + zi)(x1 + z′i + zi)(xm + z″i + zi) (yk in essence refers to ¬ xk). If (¬xk + xl + xm) is satisfiable with the 1in3 condition, then c′i is satisfiable with the 1in3 condition and vice versa. It should be noted that one of yk or xk will be 0 and the other 1 and zi has to be 0. The values of z′i, z″i can be properly chosen to satisfy the 1in3 condition. If ci is of the form (¬xk + ¬xl + xm) with two of the literals negated, c′i consists of (yk + yl + xm)(yk + xk + zi)(yl + xl + zi)(xm + z′i + zi). Again, it can be checked that if ci is satisfiable with the 1in3 condition then c′i is satisfiable with the 1in3 condition and vice versa. Note that one of yk, xk is 0 and the other 1 as also one of yl, xl is 0 and the other 1 and zi = 0. z′i assumes suitable value to satisfy the 1in3 condition. If ci is of the form (¬xk+¬xl+¬xm) will all three literals negated, c′i consists of (yk + yl + ym)(yk + xk + zi)(yl + xl + zi)(ym + xm + zi). Again, it can be checked that if ci is satisfiable with the 1in3 condition c′i is satisfiable with the 1in3 condition and vice versa. Also zi = 0 and one of yj, xj(j = k, l, m) is 0 and the other 1, and it is straightforward to see that w′ can be constructed from w0 in polynomial time. Hence, positive 1in3SAT is NP-complete.
5.	Exact cover by three-sets (X3C): Given a set with 3n elements for some natural number n and a collection of subsets of the set, each of which contains exactly three elements, do there exist in the collection n subsets that together cover the set? Show that this problem is NP-complete.
Solution.	Membership in NP is obvious. Select a set of n three-sets and check whether they cover the given set. To show X3C is NP-complete, we reduce positive 1in3SAT to it. Let us consider an instance of positive 1in3SAT with n variables and k clauses. This instance of positive 1in3SAT will be converted to a X3C instance with 18k elements and 15k three-sets such that positive 1in3SAT instance is satisfiable if and only if the X3C instance has a ‘yes’ answer. i.e., an exact cover with n three-sets is present. For each clause c = (x + y + z) we set up six elements xc, yc, zc, tc, f′c, f″c. The first three will represent the three literals, while the other three will distinguish the true literal from the two false literals. For each variable, we construct a component with two attaching points (one corresponding to true and the other to false) for each of its occurrences. See Figure 12.2. Figure 12.2. x is the variable occuring 4 times Let variable x occur nx times in the Boolean expression. We set up 4nx elements of which 2nx will be used as attaching points while the other will ensure consistency. Call the attaching points and for 1 ≤ i ≤ nx; call the other point , 1 ≤ i ≤ 2nx. Now, we construct three-sets. The component associated with variable x has 2nx sets: Suppose there are n variables x1, ..., xn, xi occurs nxi times say. Then, nx1 + nx2 +... + nxn = 3k as there are k clauses. So the number of three-sets formed is 2(nx1 + ...+nxn)=6k. Also, corresponding to each clause c = (x + y + z), we make nine three-sets, three for each literal. The first of these sets, if picked for the cover indicates that the associated literal is the one set to true in the clause; for literal x in clause c, this set is for some attaching point i. If one of the other two is picked, the associated literal is set to false; for literal x, they are . So for (x + y + z) we have: for some i, j, k. So, totally we have 6k + 9k = 15k three sets. We have element and for 1 ≤ i ≤ nx. Hence, the number of such elements is 2 * 3k = 6k. Number of elements of the for , 1 ≤ j ≤ 2nx is 2. Σnx = 2.3k = 6k. Hence, totally we have 18k elements. Note that, for each variable x, the element can be covered only by one of the two sets or . If the first is chosen, then the second cannot be chosen, so that the element , must be covered by the only other three-set in which it appears, namely, . Continuing this chain of reasoning, we see that the choice of cover for entirely determines the cover for all . In this, all are included and all are excluded or all are included and all are excluded. Thus, a covering of the components associated with variables corresponds to a legal truth assignment, where the concerned elements correspond to the complement values. Considering the components associated with clauses, we note that exactly three of the nine sets must be selected for the cover. Whichever set is selected to cover the element, tc must include a true literal, thereby ensuring that at least one literal per clause is true. The other two sets chosen cover f′c and f″c and thus, contain one false literal each, ensuring that at most one literal per clause is true. It can be seen that the construction of the sets can be done in polynomial time, given an instance of positive 1in3SAT. Note that there are 18k elements and 15k three-sets. Out of the 15k three-sets, we must select 6k to get an exact cover. For each clause, 3 three-sets are chosen amounting to 3k three-sets. For each variable x occurring nx times, nx three-sets are chosen involving elements of the form . The number of such three-sets is . Hence, totally we select 3k + 3k = 6k three-sets and by our choice they are disjoint and hence form an exact cover.

Exercises 1. The notion of a crossing sequence – the sequence of states in which the boundary between two cells is crossed – was introduced in Chapter 6 with regard to two-way FSA. The notion can be extended to TM. Prove the following about crossing sequences. The time taken by single-tape TM M on input w is the sum of the lengths of the crossing sequences between each two cells of M’s tape. Suppose M is a single tape TM which accepts an input after reading the whole input and reaches the accepting state when the tape is in a cell to the right of the cells where the input was originally placed. Show that if M accepts input w1w2, and the crossing sequence between w1 and w2 is the same as that between x1 and x2 when M is given input x1, x2, then M accepts x1w2. 2. Discuss how many steps a single-tape TM will require to accept {wcwR|w ∊ {a, b}*} {wcw|w ∊ {a, b}*} 3. Show that the following functions are fully time and space constructible n2 2n n! 4. Show that the following problems are NP-complete. Let G = (V, E) be an undirected graph. A vertex cover of G is a subset S ⊆ V such that each edge of G is incident upon some vertex in S. Does an undirected graph have a vertex cover of size k, |S| = k? A Hamilton circuit is a cycle of G containing every vertex of V. Does an undirected graph have a Hamilton circuit? G is k-colorable if there exists an assignment of the integers 1, 2, ..., k, called “colors,” to the vertices of G such that no two adjacent vertices are assigned the same color. The chromatic number of G is the smallest integer k such that G is k-colorable. Is an undirected graph k-colorable? Let G″ = (V′, E′) be a directed graph. A feedback vertex set is a subset S′ ⊆ V′ such that every cycle of G′ contains a vertex in S′. Does a directed graph have a feedback vertex set with k members? A feedback edge set is a subset F′ ⊆ E′ such that every cycle of G′ contains a edge in F′. Does a directed graph have a feedback edge set with k members? A directed Hamilton circuit is a cycle containing every vertex of V. Does a directed graph have a directed Hamilton circuit? 5. Consider the following problems: Not-all-equal 3SAT(NAE3SAT) has the same description as 3SAT, except that a satisfying truth assignment may not set all three literals of any clause to true. This constraint results in a symmetric problem: the complement of a satisfying truth assignment is a satisfying truth assignment. Maximum cut (MxC): Given an undirected graph and a positive integer bound, can the vertices be partitioned into two subsets such that the number of edges with endpoints in both subsets is no smaller than the given bound? Partition: Given a set of elements, each with a positive integer size, and such that the sum of all element sizes is an even number, can the set be partitioned into two subsets such that the sum of the sizes of the elements of one subset is equal to that of the other subset? Art Gallery (AG): Given a simple polygon, P, of n vertices and a positive integer bound, B ≤ n, can at most B “guards” be placed at vertices of the polygon in such a way that every point in the interior of the polygon is visible to at least one guard? (A simple polygon one with a well-defined interior; a point is visible to a guard if and only if the line segment joining the two does not intersect any edge of the polygon). Show that these problems are NP-complete.