91影视

Problem 8.13 showedthat ${\mathbf{A}}_{\mathrm{LBA}}$is $\mathbf{PSPACE}\mathbf{-}$complete.

a) Do we know whether${\mathbf{A}}_{\mathrm{LBA}}\mathbf{鈭�}\mathit{N}\mathit{L}$?Explain your answer.

b) Do we know whether${\mathbf{A}}_{\mathrm{LBA}}\mathbf{鈭�}\mathit{P}$ ?Explain your answer.

Show that the language $\mathbf{MAX}\mathbf{-}\mathbf{CLIQUE}$from problem 7.48 isin.${\mathbf{P}}^{\mathrm{SAT}}$

Describe the error in the following fallacious 鈥減roof鈥� that.$\mathbf{P}鈮�\mathbf{NP}$Assume that P=NP and obtain a contradiction. If P=NP, then SAT? P and so, for some k,SAT?$\mathbf{TIME}\mathbf{(}{\mathbf{n}}^k\mathbf{)}$Because every language in NP is polynomial time reducible to SAT, you have$\mathbf{NP}\mathbf{鈯�}\mathbf{TIME}\mathbf{(}{\mathbf{n}}^k\mathbf{)}$

. Therefore,.$\mathbf{P}鈯�\mathbf{TIME}\mathbf{(}{\mathbf{n}}^k\mathbf{)}$Butby the time hierarchy theorem, TIME(n k+1) contains a language that isn鈥檛 in ,$\mathbf{TIME}\mathbf{(}{\mathbf{n}}^k\mathbf{)}$ which contradicts.$\mathbf{P}鈯�\mathbf{TIME}\mathbf{(}{\mathbf{n}}^k\mathbf{)}$Therefore, $P鈮�NP.$

Consider the following function $\mathbf{pad}\mathbf{:}\mathbf{鈭�}\mathbf{*}\mathbf{脳}\mathbf{螡}\mathbf{鈫�}\mathbf{鈭�}\mathbf{*}{\mathbf{\#}}^{\mathbf{*}}$that is defined as follows. Let PAD (s, l) = s#³, where j = max (0,l - m) and mis the length of s. Thus, pad (s, l)simply adds enough copies of the new symbol # to the end of s so that the length of the result is at least l. For any language A and function $\mathit{f}\mathbf{:}\mathit{N}\mathbf{鈫�}\mathit{N}$, define the language pad(A, f) as$\mathbf{pad}\mathbf{(}\mathbf{A}\mathbf{,}\mathbf{f}\mathbf{)}\mathbf{=}\mathbf{\{}\mathbf{pad}\mathbf{(}\mathbf{s}\mathbf{,}\mathbf{f}\mathbf{(}\mathbf{m}\mathbf{\left)}\mathbf{\right)}\mathbf{|}$ where $\mathbf{s}\mathbf{鈭�}\mathbf{A}$and 鈥榤鈥� is the length of 鈥榮鈥� }. Prove that if $\mathbf{A}\mathbf{鈭�}\mathbf{TIME}\mathbf{\left(}{\mathbf{n}}^{\mathbf{6}}\mathbf{\right)}$, then $\mathbf{pad}\mathbf{(}\mathbf{A}\mathbf{,}{\mathbf{n}}^{\mathbf{2}}\mathbf{)}\mathbf{鈭�}\mathbf{TIME}\mathbf{\left(}{\mathbf{n}}^{\mathbf{3}}\mathbf{\right)}$.

Prove that if$\mathbf{NEXPTIME}\mathbf{鈮�}\mathbf{EXPTIME}$, then $\mathbf{P}\mathbf{鈮�}\mathbf{NP}$. You may find the function pad, defined in problem 9.13, to be helpful.

Prove that $\mathbf{TQBF}\mathbf{鈭�}\mathbf{SPACE}\left(n^{1/3}\right)$

Question: Read the definition of a 2DFA (two-headed finite automation) given in Problem 5.26. Prove that P contains a language that is not recognisable by a 2DFA.

Prove that $\mathbf{TIME}\mathbf{(}{\mathbf{2}}^n\mathbf{)}\mathbf{=}\mathbf{TIME}\mathbf{(}{\mathbf{2}}^{n+1}\mathbf{)}$

Suppose that A and B are two oracles. One of them is an oracle for TQBF, but if you don鈥檛 know which. Give an algorithm that has access to both A and B, and that is guaranteed to solve TQBF in polynomial time.