There is a Turing transducer T that transforms problem PI into problem P2. T has

Question

There is a Turing transducer T that transforms problem PI into problem P2. T has one read-only input tape, on which an input of length n is placed. T has a read-write scratch tape on which it uses O(S(n)) cells. T has a write-only output tape, with a head that moves only right, on which it writes an output of length O(U(n)). With input of length n. T runs for O(T(n)) time before halting. You may assume that each of the upper bounds on space and tune used are as tight as possible. A given combination of S(n). U(n). and T(n) may: 1. Imply that T is a polynomial-time reduction of P1 to P2. 2. Imply that T is NOT a polynomial-time reduction of P1 to P2. 3. Be impossible: i.e., there is no Turing machine that has that combination of tight bounds on the space used, output size, and running tune. What are all the constraints on S(n). U(n), and T(n) if T is a polynomial-time reducer? What are the constraints on feasibility, even if the reduction is not polynomial-time? After working out these constraints, identify the true statement from the list below. a) S(n) = n^2; U(n) = n^3; T(n) = n4 is possible, but not a polynomial-time reduction. b) S(n) = n^2; U(n) = n^2; T(n) = n! is possible, but not a polynomial-time reduction. c) S(n) = log n: U(n) = n; T(n) = n^2 is not physically possible. d) S(n) = log n; U(n) = n: T(n) = n^2 is possible, but not a polynomial-time reduction.

Explanation / Answer

3a) S(n) = n^2; U(n) = n^3; T(n) = n^4 is possible, but not a polynomial time reduction.

This is true since it is possible that for each of n inputs, the scratch tape is used O(n) times, so, S(n) = n^2. The output and time complexity can also be multiple of n and higher than the scratch tape usage.

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.