###### Introduction to the Theory of Computation

72 SOLVED PROBLEMS

Question: 1.7

Question: 10.16

## Prove that for any integer p > 1, if p isn’t pseudoprime, then p fails the Fermat test for at least half of all numbers in Zp^+ . ...

Call a a witness if it fails the Fermat test for p...
Question: 10.7

## Show that BPP ⊆ PSPACE. ...

If M is a probabilistic TM that runs in polynomial...
Question: 9.15

## Define pad as in Problem 9.13. a. Prove that for every A and natural number k, A ∈ P iff pad(A, n^k) ∈ P. b. Prove that P ≠ SPACE(n). ...

(a) Let A be any language and k ∈ N. If A ∈ P, the...
Question: 9.7

## Give regular expressions with exponentiation that generate the following languages over the alphabet {0,1}. 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 ...

(a) $\Sigma ^{500}$; (b) (\Sig...
Question: 9.3

## Prove that NTIME(n) ⊊ PSPACE. ...

$NTIME(n)\subseteq NSPACE(n)$ because...
Question: 9.2

## Prove that TIME(2^n) ⊊ ( TIME(2^2n). ...

The containment TIME (2^{n}) ⊆ TIME (2^{2n+...
Question: 6.3

## Show that if A ≤T B and B ≤T C, then A ≤T C. ...

Say that $M^{B}_{1}$ decides A and [l...
Question: 5.30

## Use Rice’s theorem, which appears in Problem 5.28, to prove the undecidability of each of the following languages. a. INFINITETM = {〈M〉 | M is a TM and L(M) is an infinite language}. ...

(a) $INFINITE_{TM}$ is a language of ...