Theory of Computation Breadth Exam Spring 1989

Directions: Answer three questions; you must answer questions 1 and 2.

1. Consider nondeterministic finite automata whose transitions are labelled with strings from some finite alphabet. In particular, transitions may be labelled with the empty string. Give an efficient algorithm for determining if a string is accepted by such an automaton. For a given alphabet, your method’s running time should be polynomial in both the length of the automaton’s description and the length of the input string.

For each n, there is an n-state nondeterministic automaton whose smallest equivalent deterministic automaton has Ω(2^{n}) states. Why does this not contradict your answer above?

2. An undirected graph is said to be bipartite if its vertices can be divided into two disjoint sets X and Y with the property that each edge in the graph links a vertex in X with a vertex in Y.

a) Show that a graph is bipartite if and only if it has no cycles of odd length.

b) Give an efficient algorithm to test if a graph is bipartite.

3. A counter is a pushdown store with one symbol, Z, which can be added (pushed) or subtracted (popped) from the store, and a special end-of-store symbol, B. When B is at the top of the store, the counter has value 0, otherwise its value is the number of Z’s on the counter.

A k-counter machine is a deterministic Turing machine with a read-only input tape, k counters, and no worktapes.

In one step, a counter machine can test which of its counters equal 0 and read the symbol under the input head. Based on this information it can move its input head left or right, add 1 to any of its counters or subtract one from any of the counters which are not 0. (Note that the machine is limited to only three operations on its counters: add 1, test if a counter equals 0; and if it does not contain 0, subtract 1. The machine cannot, for example, compare the value of two counters).

a) A 2-way deterministic pushdown automaton is a deterministic pushdown automaton that can move its input head either one cell to the left or one cell to the right in a step. Show that any language accepted by a 2-way deterministic pushdown automaton can be accepted by a 2-counter automaton. You can assume that the stack alphabet of the pushdown automaton is {0, 1}. (Hint: When the stack contains a_{0}a_{1} … a_{n}, with a_{0} at the top of the stack and a_{n} at the bottom, one of the counters should have the value C = ∑_{i=0}^{n} a_{i}2^{i}. Show how to use the other counter to simulate a pop and a push operation of the pushdown automaton).

b) Extend your construction in a) to show that any language accepted by a deterministic two-stack automaton – a 2-way deterministic pushdown automaton with two stacks – can be accepted by a 4-counter automaton.

c) What is the class of languages accepted by 4-counter automata? Prove your answer.

4. In an undirected graph, a set X of vertices is said to be independent if no edge connects two vertices in X. A vertex cover is a set of vertices that meets every edge. A matching is a set of edges, no two of which share a common vertex.

a) It is often stated that “finding the largest independent set is NP-complete.” Explain carefully what this means.

b) For bipartite graphs, it can be shown that the size of the smallest vertex cover equals the size of the largest matching. (You need not prove this.) Using this fact, give a polynomial-time algorithm for finding a largest independent set in a bipartite graph, as follows. i) Show that X is independent iff X̄ (the complement of X) is a vertex cover. ii) Give a polynomial time algorithm for finding the size of the largest independent set. You can assume a polynomial-time algorithm for finding the size of the largest matching is available as a “black box.”

iii) Now use the algorithm designed above to efficiently construct a largest independent set.

5. A digital search tree is a binary tree that is commonly used in radix searching. To store alphabetic characters in such a tree we assign them a binary representation. For example, we might assign five bit numbers to each letter, giving A the binary representation of 1 and Z the representation of 26. The figure below shows the digital search tree that would result if we began with an empty tree and inserted the letters A, S, E, R, C, H, I, N, G, X, M, P, L in the order listed.

A 00001 S 10011 E 00101 R 10010 C 00011 H 01000 I 01001 N 01110 G 00111 X 11000 M 01101 P 10000 L 01100

Notice that the branches of the search tree are labelled with 0 or 1 and that a new element is added by placing it on the path to the root that is labelled with a prefix of its representation. Because of this, and the fact that we assigned A the binary representation of 1 and Z the binary representation for 26, each level of the digital search tree contains characters that are lexicographically sorted from left to right.

Design an algorithm that will take a digital search tree such as the one that we have described as input and produce as output a list containing the elements in the search tree in lexicographic sorted order. You may assume that the digital search tree is stored in an array, that is, if a node is stored in location i then its children are stored in locations 2i and 2i + 1 (a value of 00000 denotes an empty child). Your algorithm should be as efficient as possible.

Theory of Computation Depth Exam Spring 1989

Directions: answer any four questions.

1. A 2-way probabilistic finite state automaton (2pfa) is the same as a 2-way deterministic finite automaton, except that the automaton may use coin-tosses. That is, the choice of next state and of direction to move the head on the input tape depends on the current state, the symbol currently under the head and whether the coin toss is heads or tails (both are equally likely).

Assume that the input w is presented on the input tape as #w#, where # is a special symbol that marks the boundaries of the input. Initially the input head is positioned on the left #. There are distinguished start, accepting and rejecting states. On accepting or rejecting, the machine halts.

The language accepted by a 2pfa is the set of all strings w such that with #w# on the input tape the 2pfa reaches the accepting state with probability ≥ 1/2. Thus for any string not accepted by the 2pfa, the probability of reaching the accepting state is < 1/2.

The language {a^{n}b^{n} | n ≥ 1} is accepted by the 2pfa described as follows.

The 2pfa repeatedly sweeps the input from left to right. On the first sweep, it verifies that the input is of the form a^{+}b^{+} and rejects if the input is not of this form. If it does not reject on the first sweep, the 2pfa initializes to 0 two variables A and B, maintained in its finite state, and then runs the following procedure on each sweep over the input.

The coin is tossed for every input symbol encountered during the sweep. We say the sweep produces a win for the a’s (b’s) if all the coins tossed while passing over the block of a’s (b’s) turn up heads. If the sweep produces a win for the a’s but not for the b’s then A := A + 1. Similarly, if the sweep produces a win for the b’s but not for the a’s, then B := B + 1.

This is repeated until A+B = 2. The input is accepted if A = B = 1 and is rejected otherwise.

a) Prove that the 2pfa specified by the above algorithm accepts the language {a^{n}b^{n} | n ≥ 1}.

b) Design a one-way probabilistic finite automaton (pfa) that accepts the language {a^{n}b^{n} | n ≥ 1}. Just as for deterministic finite automata, a pfa can only scan the input once from left to right.

2. A two-person pebble game is played on the vertices of a directed acyclic graph by two players, called the Challenger and the Pebbler. The rules of the game are as follows. The Challenger begins the game by challenging any vertex. The game now proceeds in rounds with each round consisting of a pebbling move followed by a challenging move. In a pebbling move, the Pebbler picks up zero or more pebbles from vertices already pebbled and places pebbles on any non-empty set of vertices. In a challenging move, the Challenger either rechallenges the currently challenged vertex, or challenges one of the vertices that aquired a pebble in the current round.

The Challenger loses the game at a vertex v if, immediately following the Challenger’s move, v is the current challenged vertex and all immediate predecessors of v have pebbles on them.

The time used by a pebble game is the number of pebble placements. The number of pebbles used by a pebble game is the maximum number of pebbles on the graph after any pebbling move. A graph can be two-person pebbled in time T with p pebbles if there is a winning strategy for the pebbler such that every possible play of the game on the graph uses time at most T and at most p pebbles.

a) Show that in any n-leaf binary tree where n ≥ 2, there is a vertex v such that |v|, the number of leaves which are descendants of v, satisfies n/3 ≤ v ≤ 2n/3.

b) Use a) to show that an n-leaf binary tree can be two-person pebbled with four pebbles in O(log n) time.

c) Show how to pebble an n-leaf binary tree with only two pebbles in O(log n) time.

3. Consider Boolean circuits that are built of gates that implement AND and XOR (the constants 0 and 1 are allowed). A circuit is called planar if its associated digraph is planar.

Show that any Boolean circuit has an equivalent circuit that is planar. How much larger is the planar equivalent circuit than the original circuit?

4. A set S is sparse if there is a polynomial p such that for all n

{x ∈ S : |x| ≤ n} ≤ p(n).

a) Show that if \overline{SAT} is polynomial many-one reducible to a sparse set S, [ \overline{SAT} ≤_{m}^{P} S ], then SAT is polynomially decidable.

b) Explain why your proof for a) did not require that there be any bound placed on the complexity of the sparse set S.

c) Explain why your proof for a) does, or why it does not, show that if SAT is polynomial many-one reducible to a sparse set then SAT is polynomially decidable. If the proof you gave for a) does not prove the result stated in c), then use the following hints

to prove the result.

d) Show that if SAT is polynomial many-one reducible to a sparse set S, then SAT is polynomial many-one reducible to some sparse set, T, in NP.

e) Assume that SAT ≤_{m}^{P} S where S is sparse and that the reduction is witnessed by a polynomially computable function g. Instead of bounding |g(\overline{SAT} ⋂ \{x : |x| ≤ n\})| by a polynomial, as in the proof for a), there is now a polynomial bounding function b that ensures

|g(SAT ⋂ {x : |x| ≤ n})| ≤ b(n);

explain why this is true. Now define the pseudo-complement of SAT as

P (\overline{SAT}) =_{def} \{⟨x, t⟩ : t ≤ b(|x|) & there exist distinct g(y_{1}) … g(y_{t})
& for each i [y_{i} ∈ SAT ⋂ {x : |x| ≤ n} and g(y_{i}) ≠ g(x)]},

and show P (\overline{SAT}) ∈ NP. Now for each n, and for each m ≤ b(n), define

P (\overline{SAT})_{n,m} =_{def} \{x : |x| ≤ n and ⟨x, m⟩ ∈ P (\overline{SAT})\}.

If m_{0} = |g(SAT) ∩ {x : |x| ≤ n}|, i.e., if m_{0} happens to be the actual number of distinct elements of S which elements of length less than or equal to n in SAT map to under g, then show that

P (\overline{SAT})_{n,m_{0}} = \overline{SAT} ⋂ \{x : |x| ≤ n\}.

Use this fact to complete the proof.

5. An undirected graph is said to be bipartite if its vertices can be divided into two disjoint sets X and Y with the property that each edge in the graph links a vertex in X with a vertex in Y.

a) Give an algorithm to test if a graph is bipartite. Your algorithm should run in linear time. Show that this is best possible.

b) A graph is called tripartite if the vertices can be divided into three disjoint sets such that each edge links a vertex in one of these sets with a vertex in another, different, such set. What can you say about the complexity of deciding if a graph is tripartite? Prove your answer.

6. In an undirected graph, a set X of vertices is said to be independent if no edge connects two vertices in X.

a) It is often stated that “finding the largest independent set is NP-complete.” Explain carefully what this means.

b) Give an algorithm for finding a largest independent set in a bipartite graph. Your algorithm should be as efficient as possible; estimate its complexity.