Math Problems Vault

Problem 6.4.5 from Du D., Ko K. "Problem Solving in Automata, Languages, and Complexity" [DuKo01]More problems in Section 6.4 "Nondeterministic Turing Machines"

Show that, for any real numbers $r \geq 1$ and $0<\epsilon <1$ ,

\operatorname {NSPACE}\left(n^{r}\right) \stackrel{\subset }{\neq } \operatorname {NSPACE}\left(n^{r+\epsilon }\right).

?

Problem 6.4.6 from Du D., Ko K. "Problem Solving in Automata, Languages, and Complexity" [DuKo01]More problems in Section 6.4 "Nondeterministic Turing Machines"

(a)(b)

?

(a)

Show that Lemma 6.31 still holds if we replace the conditions $s_{2}(n) \geq n$ and $f(n) \geq n$ by $s_{2}(n) \geq \log n$ and $\log (f(n))= O\left(s_{2}(n)\right)$ . [Hint: Note that NTM $M_{3}$ can simulate $M_{2}$ on input $y=x S^{f(\left|x\right|)-\left|x\right|}$ without writing down the string $y$ on the second tape. Instead, it may simply write down, in the second tape, the position $k$ of the input tape head of $M_{2}$ and use $k$ to determine what input symbol $M_{2}$ 's tape head is scanning.]

(b)

Show that, for any real numbers $r>0$ and $0<\epsilon <1$ ,

\operatorname {NSPACE}\left(n^{r}\right) \stackrel{\subset }{\neq } \operatorname {NSPACE}\left(n^{r+\epsilon }\right).

Problem 6.4.7 from Du D., Ko K. "Problem Solving in Automata, Languages, and Complexity" [DuKo01]More problems in Section 6.4 "Nondeterministic Turing Machines"

Show that if $t_{1}(n), t_{2}(n)$ , and $f(n)$ are fully time-constructible functions with $t_{2}(n) \geq n$ and $f(n) \geq n$ , then $\operatorname {NTIME}\left(t_{1}(n)\right) \subseteq \operatorname {NTIME}\left(t_{2}(n)\right)$ implies $\operatorname {NTIME}\left(t_{1}(f(n))\right) \subseteq \operatorname {NTIME}\left(t_{2}(f(n))\right)$ .

?

Problem 6.4.8 from Du D., Ko K. "Problem Solving in Automata, Languages, and Complexity" [DuKo01]More problems in Section 6.4 "Nondeterministic Turing Machines"

(a)(b)

?

(a)

Show that $\mathrm{EXP} \neq \mathrm{NP}$ .

(b)

Show that EXP $\neq \bigcup_{c>0} \operatorname {DTIME}\left(2^{n^{c}}\right)$ .

Problem 6.4.9 from Du D., Ko K. "Problem Solving in Automata, Languages, and Complexity" [DuKo01]More problems in Section 6.4 "Nondeterministic Turing Machines"

Show that if $P=\mathrm{NP}$ , then

\bigcup _{c>0} \operatorname {DTIME}\left(2^{n^{c}}\right)=\bigcup _{c>0} \operatorname {NTIME}\left(2^{n^{c}}\right).

?

Problem 9.13 from Sipser M. "Introduction to the Theory of Computation" [Sip13]More problems in Section 9.2 "Problems"

Consider the function pad : $\Sigma^{*} \times \mathcal{N} \longrightarrow \Sigma^{*} \#^{*}$ that is defined as follows. Let $\operatorname {pad}(s, l)=s \#^{j}$ , where $j=\max (0, l-m)$ and $m$ is the length of $s$ . Thus, $\operatorname {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 $f: \mathcal{N} \longrightarrow \mathcal{N}$ , define the language $\operatorname {pad}(A, f)$ as

\operatorname {pad}(A, f)=\left\{ \operatorname {pad}(s, f(m)) \mid \text{ where } s \in A \text{ and } m \text{ is the length of } s\right\} .

Prove that if $A \in \operatorname {TIME}\left(n^{6}\right)$ , then $\operatorname {pad}\left(A, n^{2}\right) \in \operatorname {TIME}\left(n^{3}\right)$ .

?

Problem 9.14 from Sipser M. "Introduction to the Theory of Computation" [Sip13]More problems in Section 9.2 "Problems"

Prove that if NEXPTIME $\neq$ EXPTIME, then $\mathrm{P} \neq \mathrm{NP}$ . You may find the function pad, defined in Problem 9.13, to be helpful.

?

Problem 9.15 from Sipser M. "Introduction to the Theory of Computation" [Sip13]More problems in Section 9.2 "Problems"

(a)(b)

ᴬ Define pad as in Problem 9.13.

Problem 9.13: Consider the function pad : $\Sigma^{*} \times \mathcal{N} \longrightarrow \Sigma^{*} \#^{*}$ that is defined as follows. Let $\operatorname {pad}(s, l)=s \#^{j}$ , where $j=\max (0, l-m)$ and $m$ is the length of $s$ . Thus, $\operatorname {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 $f: \mathcal{N} \longrightarrow \mathcal{N}$ , define the language $\operatorname {pad}(A, f)$ as

\operatorname {pad}(A, f)=\left\{ \operatorname {pad}(s, f(m)) \mid \text{ where } s \in A \text{ and } m \text{ is the length of } s\right\} .

?

(a)

Prove that for every $A$ and natural number $k, A \in \mathrm{P}$ iff $\operatorname {pad}\left(A, n^{k}\right) \in \mathrm{P}$ .

(b)

Prove that $\mathrm{P} \neq \operatorname {SPACE}(n)$ .

Padding argument

References