Text: Intro. to the Theory of Computation by M. Sipser.

Syllabus: Terminology, background, and proofs of the following ...

Theorem 1. (Myhill, Nerode) A language L is regular if and only if the

associated equivalence relation R

L

has finitely many equivalence classes.

Theorem 2. (Hennie) Let L be the language over the alphabet {a,b,c}

defined by

def

= {wc

|w|

rev

: w ∈ {a,b}

*

}.

If T is a deterministic Turing machine with q states that recognizes L,

then for each integer n ≥ log

2

q there is a string w ∈ L of length 3n such

that on input w the machine T executes at least n

2

/log q steps before

halting.

Theorem 3. (Cook, Levin) The language SAT is NP-complete.

Theorem 4. (Shannon) For each ϵ > 0, almost all Boolean functions

of n variables have circuit complexity greater than (1 − ϵ)2

/n.

Theorem 5. (Church) The theory (N,+,×) is undecidable.

Theorem 6. (Savitch) For f(n) ≥ log n,

NSPACE(f(n)) ⊆ SPACE(f(n)

2

)

Theorem 7. (Immerman, Szelepcsenyi) NL = coNL.

Theorem 8. (Shamir) IP=PSPACE.

Theorem 9. (Hartmanis) For suitable oracles A and B we have

P

A

= NP

A

P

B

≠ NP

B