Intractability

ᴬ Prove that $\operatorname {TIME}\left(2^{n}\right)=\operatorname {TIME}\left(2^{n+1}\right)$.

ᴬ Prove that $\operatorname {TIME}\left(2^{n}\right) \subsetneq \operatorname {TIME}\left(2^{2 n}\right)$.

ᴬ Prove that $\operatorname {NTIME}(n) \subsetneq \operatorname {PSPACE}$.

Show how the circuit depicted in Figure 9.26 computes on input 0110 by showing the values computed by all of the gates, as we did in Figure 9.24.

Give a circuit that computes the parity function on three input variables and show how it computes on input 011.

Prove that if $A \in \mathrm{P}$, then $\mathrm{P}^{A}=\mathrm{P}$.

Give regular expressions with exponentiation that generate the following languages over the alphabet $\left\{ 0,1\right\}$.

If $R$ is a regular expression, let $R^{\left\{ m, n\right\} }$ represent the expression

Show how to implement the $R^{\left\{ m, n\right\} }$ operator, using the ordinary exponentiation operator, but without "…".

Show that if $\mathrm{NP}=\mathrm{P}^{\text{SAT }}$, then $\mathrm{NP}=$ coNP.

Problem 8.13 showed that $A_{\text{LBA }}$ is PSPACE-complete.

Show that the language MAX-CLIQUE from Problem 7.48 is in $\mathrm{P}^{\text{SAT }}$.

Problem 7.48: MAX-CLIQUE $=\left\{ \langle G, k\rangle \mid \text{ a largest clique in }G\text{ is of size exactly }k\right\}$.

Describe the error in the following fallacious "proof" that $\mathrm{P} \neq \mathrm{NP}$. Assume that $\mathrm{P}=\mathrm{NP}$ and obtain a contradiction. If $\mathrm{P}=\mathrm{NP}$, then SAT $\in \mathrm{P}$ and so for some $k$, $S A T \in \operatorname {TIME}\left(n^{k}\right)$. Because every language in NP is polynomial time reducible to $S A T$, you have $\mathrm{NP} \subseteq \operatorname {TIME}\left(n^{k}\right)$. Therefore, $\mathrm{P} \subseteq \operatorname {TIME}\left(n^{k}\right)$. But by the time hierarchy theorem, $\operatorname {TIME}\left(n^{k+1}\right)$ contains a language that isn't in $\operatorname {TIME}\left(n^{k}\right)$, which contradicts $\mathrm{P} \subseteq \operatorname {TIME}\left(n^{k}\right)$. Therefore, $\mathrm{P} \neq \mathrm{NP}$.

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

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)$.

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.

ᴬ 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

Prove that $T Q B F \notin \operatorname {SPACE}\left(n^{1 / 3}\right)$.

• Read the definition of a 2DFA (two-headed finite automaton) given in Problem 5.26. Prove that P contains a language that is not recognizable by a 2DFA.

Problem 5.26: A two-headed finite automaton (2DFA) is a deterministic finite automaton that has two read-only, bidirectional heads that start at the left-hand end of the input tape and can be independently controlled to move in either direction. The tape of a 2DFA is finite and is just large enough to contain the input plus two additional blank tape cells, one on the left-hand end and one on the right-hand end, that serve as delimiters. A 2DFA accepts its input by entering a special accept state.

Let $E_{\text{REX } \uparrow }=\left\{ \langle R\rangle \mid R\text{ is a regular expression with exponentiation and }L(R)=\emptyset \right\}$. Show that $E_{\text{REX } \uparrow } \in$ P.

Define the unique-sat problem to be

Show that USAT $\in \mathrm{P}^{S A T}$.

Prove that an oracle $C$ exists for which $\mathrm{NP}^{C} \neq \operatorname {coNP}^{C}$.

A k-query oracle Turing machine is an oracle Turing machine that is permitted to make at most $k$ queries on each input. A $k$-query oracle Turing machine $M$ with an oracle for $A$ is written $M^{A, k}$. Define $\mathrm{P}^{A, k}$ to be the collection of languages that are decidable by polynomial time $k$-query oracle Turing machines with an oracle for $A$.

Suppose that $A$ and $B$ are two oracles. One of them is an oracle for $T Q B F$, but you don't know which. Give an algorithm that has access to both $A$ and $B$, and that is guaranteed to solve TQBF in polynomial time.

Recall that you may consider circuits that output strings over $\left\{ 0,1\right\}$ by designating several output gates. Let $\operatorname {add}_{n}:\left\{ 0,1\right\}^{2 n} \longrightarrow \left\{ 0,1\right\}^{n+1}$ take two $n$ bit binary integers and produce the $n+1$ bit sum. Show that you can compute the $\operatorname {add}_{n}$ function with $O(n)$ size circuits.

Define the function $\operatorname {majority}_{n}:\left\{ 0,1\right\}^{n} \longrightarrow \left\{ 0,1\right\}$ as

Thus, the $\operatorname {majority}_{n}$ function returns the majority vote of the inputs. Show that $\operatorname {majority}_{n}$ can be computed with:

• Define the function $\operatorname {majority}_{n}$ as in Problem 9.24. Show that it may be computed with $O(n)$ size circuits.

Problem 9.24: The function $\operatorname {majority}_{n}:\left\{ 0,1\right\}^{n} \longrightarrow \left\{ 0,1\right\}$ is

Thus, the $\operatorname {majority}_{n}$ function returns the majority vote of the inputs.