# 计算理论代写 | Computational Theory Homework

### 计算理论代写 | Computational Theory Homework

1. (Hierarchy Theorems) You may assume without saying so that any reasonable-looking function (logarithms, polynomials, exponentials, and combinations thereof) are time-constructible.

(a) Show that P ⊆ TIME(nlog n).

(b) Use the time hierarchy theorem to show that EXP ̸⊆ TIME(nlog n).

(c) Combine parts (a) and (b) to conclude that P ̸= EXP.

2. (Fun with Encodings)

(a) Prove that there is no polynomial-time algorithm that takes as input a natural number n (written in binary) and outputs (i.e., writes to its tape) the number n! (again, written in binary).

Hint: Explain why the expected output for this problem is so long that it is impossible for a poly-time algorithm to even write it down.

(b) Give a high-level description of a polynomial-time algorithm that takes as input a natural number n (written in unary) and outputs the number n! (written in binary). Explain why your algorithm is correct and why it runs in polynomial time.

Hint: You can use without proof the fact that Turing machines can perform basic arithmetic operations on binary numbers, like addition and multiplication, in polynomial time.

3. (Polynomial-Time Algorithms)

(a) Let A = {wwR | w ∈ {0,1}∗}. Show that A ∈ TIME(n2) and A ∈ SPACE(n) by i) giving an implementation-level description of a basic, single-tape Turing machine M that decides A, ii) briefly explain why your TM correctly decides A, and iii) analyzing the running time and space usage of M.

(b) If G = (V,E) is an undirected graph, and u,v are vertices in V , let dG(u,v) denote the length of the shortest path from u to v in G. (Define dG(u,v) = ∞ if no path exists.) Let CLOSER = {⟨G,u,v,w⟩ | G is an undirected graph,u,v,w are vertices, and dG(u,v) < dG(u,w)}. This corresponds to the following computational problem: Given a graph G and vertices u,v,w, is u closer to v than it is to w?

Show that CLOSER ∈ P by i) giving a high-level description of a polynomial-time algorithm deciding CLOSER, ii) analyzing the correctness of your algorithm, and iii) explaining why your algorithm runs in polynomial time.

You don’t need to specify the exact polynomial runtime that your algorithm runs in, since this may depend on implementation details that are suppressed in a high-level description. Just give a convincing argument that the runtime is polynomial as in the examples in Chapter 7.2 of Sipser.

4. (Closure Properties)

(a) Show that P is closed under the union operation.

(b) This part of the problem will walk you through a proof that P is closed under the star operation. Let L be a language in P, and let M be a TM deciding L in time O(nc) for some constant c. Consider the following algorithm S1 that decides L∗. Explain why S1 does not run in

polynomial time.

Algorithm: S1(w)

Input : String w = w1w2 …wn of length n

1. For each way to break w into a concatentation of strings s1 ◦ s2 ◦ ··· ◦ sk (for k ≤ n):

2. For each i = 1,…,k:

3. Run M on input si.

4. If all runs have accepted, accept.

5. Reject.

(c) The following recursive algorithm uses a slightly different idea. Its correctness relies on the fact that a string w1w2 …wn ∈ L∗ if and only if there exists an index i ∈ {0,…,n − 1} such that w1w2 …wi ∈ L∗ and wi+1 …wn ∈ L. Explain why S2 does not run in polynomial time.

Algorithm: S2(w)

Input : String w = w1w2 …wn of length n

1. If n = 0:

2. Run M on input ε. If it accepts, accept. If it rejects, reject.

3. For each i = 0,1,2,…,n − 1:

4. Run S2 on input w1w2 …wi and run M on input wi+1 …wn.

5. If both runs accept, accept.

6. Reject.

(d) The main issue with the recursive algorithm in part (c) is that it for each prefix w1w2 …wi of w, it keeps repeating the work of checking whether that prefix is in L∗. Wouldn’t it be great if for each i, you only had to check whether w1w2 …wi is in L∗ once?

It turns out you can, and this forms the basis of an actual polynomial time algorithm. Think of filling out an array T[0,1,…,n] where each cell T[i] contains the answer to the question, “is w1w2 …wi ∈ L∗?” Design an algorithm S3 that systematically fills in this array and uses it to determine whether w ∈ L∗. Briefly explain why your algorithm runs in polynomial time, and how it allows you to conclude that P is closed under the star operation.

5. (Bonus problem) Show that your algorithm from problem 3(a) is optimal: There is no basic, single-tape TM algorithm deciding the language A = {wwR | w ∈ {0,1}∗} in time o(n2).