Question

Under the assumption that there exists an unknown Turing machine encodableinc1bits that decides3-SATis inO(n10) time, give implementation details for a Turing Machine M that decides 3-SAT in O(n10000) time.

Answer 1

Answer:

3. (9 points) The goal of this problem is to show that our formal definitions of P and NP imply that P = NP cannot have a non-constructive proof. Throughout this problem we assume a consistent, binary, encoding of both Turing machines and 3-SAT instances. Note that the complexities are intentionally not tight to address potential overheads from scan- ning the tape linearly in order to look for certain symbols. (a) (3 points) Show that for any constant cı, there is a constant c2 such that if Mi is a Turing machine encoded by at most bits that correctly decides 3-SAT in O(n10) time (aka. 3-SAT E TIME(n10), then there is a Turing machine M, encoded by at most most c2 bits that runs in O(n100) time such that if the 3-SAT instance has a satisfying assignment, M, accepts and writes a satisfying assignment at the end of the tape. (b) (3 points) Let M ...Mbe Turing machines show that the language {(k, M... Mk,t,w) | w is an instance of 3-SAT and one of M, writes a satisfying assignment to w in at most t steps can be decided by a Turing machine in (k2107 10) time. (c) (3 points) Under the assumption that there exists an unknown Turing machine encodable in c bits that decides 3-SAT is in O(n10) time, give implementation details for a Turing Machine M that decides 3-SAT in O(n10000) time. Hint: the constant factor in the big-O is able to hide any function related ci and c2, which independent of input sizes, and thus constants.

Explanation:

3. (9 points) The goal of this problem is to show that our formal definitions of P and NP imply that P = NP cannot have a non-constructive proof. Throughout this problem we assume a consistent, binary, encoding of both Turing machines and 3-SAT instances. Note that the complexities are intentionally not tight to address potential overheads from scan- ning the tape linearly in order to look for certain symbols. (a) (3 points) Show that for any constant cı, there is a constant c2 such that if Mi is a Turing machine encoded by at most bits that correctly decides 3-SAT in O(n10) time (aka. 3-SAT E TIME(n10), then there is a Turing machine M, encoded by at most most c2 bits that runs in O(n100) time such that if the 3-SAT instance has a satisfying assignment, M, accepts and writes a satisfying assignment at the end of the tape. (b) (3 points) Let M ...Mbe Turing machines show that the language {(k, M... Mk,t,w) | w is an instance of 3-SAT and one of M, writes a satisfying assignment to w in at most t steps can be decided by a Turing machine in (k2107 10) time. (c) (3 points) Under the assumption that there exists an unknown Turing machine encodable in c bits that decides 3-SAT is in O(n10) time, give implementation details for a Turing Machine M that decides 3-SAT in O(n10000) time. Hint: the constant factor in the big-O is able to hide any function related ci and c2, which independent of input sizes, and thus constants.