Homework answers / question archive / 1) A decision problem X is self-solvable if X = L (Mx) for some polynomial-time oracle TM M, whose oracle queries are always strictly shorter than its input

1) A decision problem X is self-solvable if X = L (Mx) for some polynomial-time oracle TM M, whose oracle queries are always strictly shorter than its input

Computer Science

Share With

1) A decision problem X is self-solvable if X = L (Mx) for some polynomial-time oracle TM M, whose oracle queries are always strictly shorter than its input. In other words, when M is executed on an input of length n, it queries its oracle only on strings of length less than n. This is a strange situation, where M has oracle access to the problem that it is trying to solve. But when M is trying to determine whether x E X, it cannot simply query its oracle on x for the answer.
(a) Show that TQBF is self-solvable. Be explicit about what assumptions are you making about how for-mulas are encoded into bit strings. (b) Prove that if L is self-solvable then L E PSPACE. (*) For super duper extra credit or something (because I just thought of this question and am not 100% sure it is possible): Construct a language L E PSPACE that is not self-solvable. 
2) A "logspace computable" function is a function computable by a deterministic TM with read-only input tape, write-only (write-once, sequential) output tape, and 0(log n)-size work tape. (a) Suppose f is a logspace computable function. Show that { (x, i) I ith bit of f(x) is 1) E L Here i is an integer represented in binary. Remember that even though f is computable in logspace, the output f (x) can be very long (polynomial in IxI). (b) Suppose f and g are both logspace computable functions. Show that h(x) = g(f (x)) is also computable in logspace. Remember that while computing h, you do not have enough space on the work tape to write down the intermediate value f (x). But you can use part (a) instead. This problem shows that the <L logspace reduction between decision problems is transitive.