Problem Detail: I’m working on old multiple choice exams and would like to know if the following statements are true or false: a) $L_1 le_p L_2 le_p L_3 Rightarrow L_1 le_p L_3$ b) If $L in mathsf{NP}$ and $U le_p L$ holds for all languages $U in mathsf{PSPACE}$ then $mathsf{NP} = mathsf{PSPACE}$ c) $L in P Leftrightarrow L le_p {a}^*$ Statement a) was part of the lecture, Statesments b) and c): I don’t know.
Asked By : David2013
Answered By : Shaull
Article (a) is badly written. Writing $L_1le_p L_2le_p L_3$ already implies, in a way, that we have transitivity. How do you think could a reduction function for $L_1le_p L_3$ look like, if we know reduction functions for $L_1le_p L_2$ and $L_2le_p L_3$? As for (b): If $Ule_p L$ for every language $Uin PSPACE$, then in particular this is true for some PSPACE complete language. For example, TQBF. Do you see what to do from here? (comment if not) For (c): Also badly written, since the alphabet isn’t stated, and it may affect the answer. Assuming the alphabet is not ${a}$, but something bigger (e.g. ${a,b}$), then the answer is yes: first, obviously if $Lle_p {a}^*$ then $Lin P$ (do you see why this is obvious?) Conversely, if $Lin P$ then you can solve $L$ “within” a polynomial-time reduction. That is, given an input for $L$, a reduction can decide whether it is in $L$, and use the result to decide what to output. Now, if the alphabet has other letters than $a$, then $a^*neq Sigma^*$, and the reduction can output something that is either in ${a}^*$ or not in ${a}^*$, depending on the input. If, however, the alphabet is ${a}$, then there is no such reduction unless $L={a}^*$.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/12889 Ask a Question Download Related Notes/Documents
