Math Problems Vault

Problem 9.1

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

?

Problem 9.2

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

?

Problem 9.3

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

?

Problem 9.4

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.

?

Problem 9.5

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

?

Problem 9.6

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

?

Problem 9.7

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

?

(a)

ᴬ All strings of length 500

(b)

ᴬ All strings of length 500 or less

(c)

ᴬ All strings of length 500 or more

(d)

ᴬ All strings of length different than 500

(e)

All strings that contain exactly 500 1s

(f)

All strings that contain at least 500 1s

(g)

All strings that contain at most 500 1s

(h)

All strings of length 500 or more that contain a 0 in the 500th position

(i)

All strings that contain two 0s that have at least 500 symbols between them

Problem 9.8

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

R^{m} \cup R^{m+1} \cup \cdots \cup R^{n}.

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

?

Problem 9.9

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

?

Problem 9.10

(a)(b)

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

?

(a)

Do we know whether $A_{\mathrm{LBA}} \in \mathrm{NL}$ ? Explain your answer.

(b)

Do we know whether $A_{\mathrm{LBA}} \in \mathrm{P}$ ? Explain your answer.

Problem 9.11

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\}$ .

?