Complexity Class Theory

Question 1

Savitch’s Theorem

Answer 1

For s(n) >= n, NSPACE(s(n)) ⊆ SPACE(s(n)^2)

Question 2

Time Constructible

Answer 2

t is time constructible if t(n) >= nlogn and if the binary representation of t(n) can be computed in time O(t(n))

Question 3

Space Constructible

Answer 3

s is space constructible if s(n) >= logn and if the binary representation of s(n) can be computed in space O(s(n))

Question 4

Space Hierarchy Theorem

Answer 4

For any space constructible s(n), there is a language L decidable in O(s(n)) space but not o(s(n)) space

Question 5

Time Hierarchy Theorem

Answer 5

For any time constructible t(n), there is a language L decidable in O(t(n)) time but not o(t(n)/log(t(n))) time

Question 6

Class L

Answer 6

SPACE(log(n)) (decidable by an O(log(n)) space TM)

Question 7

Witness problem for class L

Answer 7

{0^(k)1^(k): k >= 0}

Question 8

Witness problem for class NL = coNL (NL-complete)

Answer 8

PATH = {<G, s, t>: G is a directed graph with path from s to t}

Question 9

Witness problem for class P (P-complete)

Answer 9

CIRCUIT-VALUE = {<C, x>: C is a boolean circuit and C(x) = 1}

Question 10

Witness problem for class NP (NP-complete)

Answer 10

SAT = {<φ>: φ is a satisfiable boolean formula}, 3SAT, CLIQUE</φ>

Question 11

Witness problem for class PSPACE = NPSPACE (PSPACE-complete)

Answer 11

TQBF = {<φ>: φ is a quantified boolean formula that evaluates to TRUE}</φ>

Question 12

Witness problem for class EXPTIME (EXPTIME-complete)

Answer 12

HALT in k

Question 13

Witness problem for class EXPSPACE (EXPSPACE-complete)

Answer 13

EQ_REX = {<Q, R>: Q, R are regular expressions with exponentiation such that L(Q) = L(R)}