The Australian National University Semester 1, 2020 Research School of Computer Science Tutorial 8
Theory of Computation
Get into groups of two, grab a whiteboard marker each, and write your names on top of your side of the board. Exercises with a ! denote harder ones, !! denotes very difficult, and !!! denotes challenge exercises beyond the scope of the course.
Exercise 1 Examples of Problems
Copyright By PowCoder代写 加微信 powcoder
For the following problems, you can assume that the Turing machine in question has as many tape symbols or tapes as you require, as a standard Turing machine can emulate a Turing machine with extra symbols or extra tapes with at most polynomial overhead. The input will initially be put on the first tape, but you can move it around to other tapes as need be.
1. Show that the addition problem (given a tuple (a,b,c) of three non-negative integers encoded in binary separated by # symbols, does a + b = c?) is in P.
Solution. We choose a three tape machine, and copy b and c to the second ad third tape (taking O(n) time).
We then read a on tape 1, b on tape 2, and c on tape 3 in sync, right to left. We compute the sum a+b, and compare each bit of the result with c. Accept iff the sum matches, which takes O(n) time.
Hence, this problem is in P.
2. (hard) Show that the multiplication problem (given a tuple (a, b, c) of three non-negative integers
encoded in binary separated by # symbols, does a × b = c?) is in P.
Choose a three tape machine, and copy b to tape 2 taking O(n) time. We then implement long multiplication, by reading a left to right. For each bit in a that is one, add b to the third tape (taking O(n) time, by following the previous algorithm).
After we’ve checked a bit in a, we add a zero to the right of b (in effect, multiplying b by 2), and repeat until we’ve read all of a. The loop runs O(n) times, for a total cost of O(n2), which is polytime.
Hence the multiplication problem is in P.
(More formally, the algorithm we are implementing is
multiply(a,b)
result = 0;
while(a != 0)
if(a & 1 == 1)
result = result + a;
b = b << 1;
a = a >> 1; }
return result;
(Note that merely adding in a loop isn’t good enough, as for a number with n bits, we much have to add at most 2n − 1 many times, which is not polynomial time.)
3. Show that the matrix multiplication problem (given a tuple (A,B,C) of matrices containing non- negative integers of dimension n × n, does AB = C?) is in P.
The matrix is encoded on the tape in row-major order (left to right, top to bottom). Elements in a row are delimited by # symbols, rows are delimited by & symbols, and the matrix is delimited by $ symbols. The dimension of the matrix is added to the front, with another $ to act as a delimiter.
Example, the matrix
a11 a12 a21 a22 a31 a32
a13 a23 a33
would be encoded as
$b(3)$b(a11 )#b(a12 )#b(a13 )&b(a21 )#b(a22 )#b(a23 )&b(a31 )#b(a32 )#b(a33 )#$
where the function b takes a non-negative integer and returns a binary string to represent it. Solution. We need to compute each element of AB, which from the definition of matrix multipli-
(AB)ij =AikBkj
Consider a 5-tape machine. First, copy A to the second tape (O(n)) and the transpose of B to the third tape. We can transpose as we copy for B, by reading out the first integer of each row, then the second integer, and so on. This will require O(n) work to copy each column, repeated as many times as there are elements in the matrix, which is bounded above by n, hence O(n).
We then use the fourth tape as a scratch tape, and compute each element of AB using the given formula. Each multiplication costs O(n2), of which there are ≤ n many, and each addition is O(n) with ≤ n many, so computing one element of AB is O(n3 + n2) = O(n3). We need to do this for every element of AB, so total cost of O(n5).
Lastly, we compare the computed AB with C, at a cost of O(n), and accept iff they are the same. Hence the matrix multiplication problem is in P.
4. Show that the sudoku problem (given a n × n grid where each cell is either blank, or contains an integer from 1 to n, does there exists integers to fill the blanks such that each row and each column contains exactly one of each integer from 1 to n?) is in NP.
The sudoku is encoded the same way as a n × n matrix.
Solution. Wew construct a machine that can verify a solution. Consider a three tape machine. Firstly, we copy the transpose of the sudoku matrix to the second tape, O(n2) time.
Secondly, we check that the first row contains all numbers from 1 to n exactly once, by copying n to the third tape, and counting down. We can check that each element is in the row once and only once in a single pass, (O(n)) so repeating for all elements from 1 to n is O(n2). Repeating for all rows is O(n3), and another O(n3) cost for the columns. The total cost is O(n3) to verify a correct answer, hence the sudoku problem is in NP.
5. (hard) Show that the primality problem (given a binary string, is the number it represents prime?) is in co-NP, i.e. that the complement of the primality problem C = {w ∈ {0,1}∗ | w is not the binary encoding of a prime number} is in P.
(Remark: it was shown in 2002 that primes are in P via the AKS primality test. Up to this point, all fast primality tests were probabilistic, they either terminated declaring the number to be composite, or with high (but not 100%) confidence that it was prime.)
You may assume you have a polynomial time algorithm to compute long division with remainder.
Solution. We need to prove that the complement problem (given a binary string, is the number it represents composite1) is in NP. That is, given a composite number, how can we verify a proof that it is composite in polynomial time?
1We can handle the annoy edge cases of 0 and 1 separately in O(1) time.
Proof that a number is composite would be to obtain a divisor d ≥ 2. So given such a number d, we can divide the given number by d (polytime) and accept if and only if the remainder is zero.
Since we have a polytime algorithm to verify answers to the complement problem, this means that the primality problem is NP.
6. Show that the travelling salesman problem (given a weighted graph G of cities with weighted edges representing roads between cities, and how much it costs to travel that road, and a budget c, does there exist a route that visits each city exactly once and returns to the origin city, at a total cost of t ≤ c?) is NP.
(Don’t worry too much about the details of how the graph is encoded on the tape, a description of an algorithm will suffice.)
Solution. As before, we use the fact that N P is equivalent to verifying a solution. A solution here would be a sequence of adjacent nodes, such that the sums of the weights on the edges traversed is ≤ c.
So, given a solution, we just add up all the weights, and check that it’s less than ≤ c. Comparison of integers is polytime, and addition is polytime, and we repeat the addition O(n) times (for each node in the graph), hence polytime.
Exercise 2 Closure properties of P Prove that P is closed under the following operations:
Solution. Given two Turing machines that run in polytime, we build a new machine that emulates the first on some input, and then emulates the second. Accept if either of the internally simulated machines accepted. Since both internal machines run in polytime, so does the outer machine.
2. Complements
Solution. Run a polytime Turing machine, and return the opposite result, which is polytime.
3. Intersection
Solution. Same as union, but accept iff both machines accept.
4. Reversal
Solution. Given a polytime machine M, first reverse the input string in O(n2) time, and then run
M, which is still polytime.
5. Concatenation
Solution. Use the same solution as the previous tutorial sheet to prove that recursive languages are closed under concatenation, noting that given an input string n, and for machines M1 and M2 with running time complexity bounded by polynomials p1(n) and p2(n), then we can bound the time to check all possible splittings of the string into two substrings by
O(n(p1(n) + p2(n))
which is still polytime. We achieve the above bound by considering that any splitting of the input string x = αβ results in two strings with lengths ≤ n, and so the combined running time of M1(α) and M2(β) is bounded above by p1(n) + p2(n) + O(n), where the linear cost is to perform the splitting and write a separator symbol in between.
Exercise 3 Closure properties of NP 1. Prove that NP is closed under the following operations:
Solution. Non-deterministically choose to run one of two machines internally, and accept if at least one of the two accepts.
(b) Intersection
Solution. Run both non-deterministic machines, and accept if they both accept,
(c) Reversal
Solution. Reverse the string in polytime, and then feed the result to the machine M
(d) Concatenation
Solution. Perform the same splitting argument as before, but now the machines are non- deterministic instead. The same argument holds.
2. It is an open problem if N P is closed under complements. Try to prove closure under complements the same way we did for P. Why doesn’t the proof work?
Solution. A non-deterministic machine accepts if there is some sequence of valid transitions it can take to halt in a final state. By complementing the states, it may not result in complementing the language, as sequences of ID’s that before lead to a non-final state now lead to a final state, and we can choose to do that path of evaluation instead.
(By analogy, think about flipping the final and non-final states of an NFA, and see if you can work out why the language might not be precisely the complement of what it was.)
We can’t do this for a deterministic Turing machine, as it’s deterministic, there’s only one valid execution trace, so by flipping the final and non-final states, the behaviour of the machine is un- changed.
Exercise 4 Alternative Definition of NP
In the lectures, we have introduced the notion of polytime verifiable using a verifier, the runtime of which only depends on the string that is tested for language membership. We have discussed briefluy that certificates only need to be polynomially long. This exercise makes this discussion precise.
Show that a problem A ⊆ Σ∗ is polynomially verifiable if and only if there exists a polynomial p and a polynomial time Turing machine M such that the following certification property holds:
Forallw∈Σ∗,wehavew∈Aifandonlyifthereexistsc∈Σ∗ with|c|≤p(|w|)and(w,c)∈L(M). Solution. First assume that A is polytime verifiable. Then there exists a TM M with the following
properties:
1. M accepts ⟨w,c⟩ for some string c iff w ∈ A
2. Running M on ⟨w, c⟩ takes at most p(|w|) many steps. It follows that
A={w∈Σ∗ |⟨w,c⟩∈L(M)forsomecwith|c|≤p(|w|)} as M can only read p(|w|) tape cells in p(|w|) many steps.
It remains to show that M itself is polytime. We have that the runtime of M on ⟨w, c⟩ is bounded by a polynomial in w, hence, as |⟨w, c⟩| ≥ |w|, it is also bounded by a polynomial in |⟨w, c⟩|.
Now we assume that A satisfies the conditions in the exercise. We need to show that A is polytime verifiable. So let M be a polytime TM and assume that M terminates in q(|w|) steps on input string w. We need to show that there exists a TM M′ such that
A={w∈Σ∗ |⟨w,c⟩∈L(M′)forsomec∈Σ∗} and the runtime of M′ is bounded by a polynomial in |w| only.
We do this by modifying M so that M , on input ⟨w, c⟩ never runs for more than q(|w| + p(|w|)) steps. If M has not terminated then, we reject. This will not affect the fact that w ∈ L if and only if there is a certificate c such that ⟨w, c⟩ ∈ L(M ), as the cerfificate – if it exists – will be at most p(|w|) characters long.
One way to achieve this is to use a two-tape TM, where on the second tape, we code the polynomial q(|w| + p(|w|)), and the first tape is the working tape. We compute, acdording to M, on the first tape, and decrement on the second tape. Converting back to a single tape machine then gives (q(|w|+p(|w|)))2 many steps, which is still a polynomial in |w|.
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com