COMP3630 / COMP6363
week 10: Other Complexity Classes
This Lecture Covers Chapter 11 of HMU: Other Complexity Classes
slides created by: Dirk Pattinson, based on material by
Peter Hoefner and Rob van Glabbeck
convenor & lecturer: Pascal Bercher
The Australian National University
Semester 1, 2023
Content of this Chapter
The classes PSPACE, NPSPACE, and their co-classes
The classes EXPTIME and NEXPTIME
PSPACE vs. NPSPACE (Savitch’s Theorem)
Relationship among these (and other) classes
Additional Reading: Chapter 11 of HMU.
Pascal Bercher week 10: Other Complexity Classes Semester 1, 2023 2 / 11
The classes PSPACE, NPSPACE, and their co-classes
Polynomial Space
Definition 11.1.1
A Turing machine M is polyspace bounded if there is a polynomial p so that for all inputs
w , M never uses more than p(|w |) tape cells when started with w .
Note.
∠ For deterministic machines, this refers to the unique computation path.
∠ For non-det. machines, this refers to all computation paths starting with input w .
Definition 11.1.2
The class PSPACE is the class of languages L such that L = L(M) for a polyspace
bounded deterministic Turing machine.
The class NPSPACE is the class of languages L such that L = L(M) for a
polyspace-bounded non-deterministic Turing machine.
Pascal Bercher week 10: Other Complexity Classes Semester 1, 2023 3 / 11
The classes PSPACE, NPSPACE, and their co-classes
Relationship to Other Classes (A first Look)
Easy Inclusions
P ⊆ PSPACE and NP ⊆ NPSPACE.
(you cannot use more than polynomially many cells in polynomial time, but can spend
more time than once on each cell).
Inclusions Unknown (to the Literature)
We don’t know whether P = PSPACE or NP = NPSPACE or neither.
Pascal Bercher week 10: Other Complexity Classes Semester 1, 2023 4 / 11
The classes PSPACE, NPSPACE, and their co-classes
Example ALLNFA
ALLNFA = {⟨A⟩ : A is an NFA and L(A) = Σ∗}
Currently, it’s known neither whether ALLNFA ∈ NP nor whether ALLNFA ∈ co-NP.
Q. Why don’t we know co-NP? A. Word can be arbitrarily (non-poly) long!
NPSPACE Algorithm for ALLcNFA – the complement, which accepts A if L(A) ̸= Σ∗
Let M implement the following non-deterministic procedure when called with input ⟨A⟩
and A = (Q,Σ, δ, q0,F ) is an NFA.
1 Mark q0 (as being visited). If q0 /∈ F , accept. // Then, ϵ /∈ L(A), thus L(A) ̸= Σ∗
2 Repeat 2|Q| times:
1 Let m ⊆ Q be the currently marked states.
2 Pick some a ∈ Σ and change m to ⋃q∈m δ(q, a).
3 If m ∩ F = ∅, accept. // Then, we found a state that’s not accepted.
// I.e., not all reachable states are accepting states, then some word wa /∈ L(A).
3 reject // Since we can’t find a word that’s rejected, so L(A) = Σ∗
∠ M may use exponential time but linear space only.
∠ Hence ALLcNFA ∈ NPSPACE – and thus, by definition, ALLNFA ∈ co-NPSPACE
Pascal Bercher week 10: Other Complexity Classes Semester 1, 2023 5 / 11
The classes PSPACE, NPSPACE, and their co-classes
PSPACE vs. co-PSPACE
Theorem 11.1.3
PSPACE = co-PSPACE (and NPSPACE = co-NPSPACE)
Proof.
∠ Let L ∈ PSPACE (resp., L ∈ co-PSPACE).
∠ Decide Lc in PSPACE (resp., Lc ∈ co-PSPACE) via:
First, decide L ∈ PSPACE (resp., L ∈ co-PSPACE).
Then, flip result. This decides Lc , taking poly-space.
∠ Intuitively, there’s no reason why result flipping should not be allowed in a space class.
The same arguments work for NPSPACE/co-NPSPACE.
Note on ALLNFA
∠ Later, we will show that PSPACE = NPSPACE.
∠ Thus, ALLNFA ∈ PSPACE.
Pascal Bercher week 10: Other Complexity Classes Semester 1, 2023 6 / 11
PSPACE and EXPTIME, NEXPTIME
Exponential Time
Definition 11.2.1
A deterministic or non-deterministic Turing machine runs in exponential time if it
terminates in at most cp(|w|) steps for a constant c and polynomial p.
EXPTIME is the class of languages L for which L = L(M) for an exptime deterministic
Turing machine.
NEXPTIME is the class of languages L for which L = L(M) for a nondeterministic
exponential time Turing machine.
(More) Easy Inclusions
Recap:
∠ P ⊆ PSPACE and NP ⊆ NPSPACE.
∠ PSPACE = co-PSPACE and NPSPACE = co-NPSPACE
Now also:
∠ EXPTIME ⊆ NEXPTIME
∠ P ⊊ EXPTIME, that’s one of the very few inclusions known to be proper
Still to show: PSPACE ⊆ EXPTIME (not that easy, but not that hard either)
Pascal Bercher week 10: Other Complexity Classes Semester 1, 2023 7 / 11
PSPACE and EXPTIME, NEXPTIME
PSPACE vs. EXPTIME
Theorem 11.2.2
PSPACE ⊆ EXPTIME
Proof.
∠ Let L ∈ PSPACE.
∠ Then, L is decided by TM M with |M| = n within O(nk) space for some constant k.
∠ How many different TM configurations can we see before running into a loop?
∠ Each cell can have at most |Γ| different symbols.
∠ So we have at most O(|Γ|(nk )) different tape configurations.
∠ We have |Q| states and at most O(nk) head positions.
∠ In total we have at most cp(n) = O(|Q| · (nk) · |Γ|(nk )) TM configurations.
∠ Since k is a constant, we need at most exponential time before running into a loop
(which we don’t have to since the problem is decided).
Pascal Bercher week 10: Other Complexity Classes Semester 1, 2023 8 / 11
PSPACE vs. NPSPACE (Savitch’s Theorem)
Savitch’s Theorem: PSPACE = NPSPACE
Note
The following is (maybe?) remarkable because we do not know whether P = NP.
Theorem 11.3.1
PSPACE = NPSPACE Savitch’s Theorem, 1970
Proof.
∠ Let L ∈ NPSPACE and M be non-det. TM, polyspace-bounded by p(n) deciding L.
∠ Noteworthy1, we are allowed to assume that M has the following properties:
M has just a single accepting state, which is a halting state.
When it accepts, the tape is empty.
Taken together, there is just a single halting configuration. (We call it J.)
∠ Recall that M has cp(n) different IDs, were n = |M|.
∠ Design a deterministic TM M ′, which decides whether I ⊢∗ J is possible within at
most cp(n) steps. M ′ is space-bounded by p(n).
∠ We formalize this via predicate P(ID1, ID2,m), initialized to P(I , J, c
p(n)).
1(Related to why we were allowed to assume that our CFL is given in Chomsky NF, cf. Theorem 10.2.9.)
Pascal Bercher week 10: Other Complexity Classes Semester 1, 2023 9 / 11
PSPACE vs. NPSPACE (Savitch’s Theorem)
Savitch’s Theorem: Recursive Doubling
Goal. Implement P(I , J,m) = I ⊢∗ J in deterministic polyspace
P(I, J, m): for all IDs K with length <= p(n) do {
if P(I, K, m/2) and P(K, J, m/2) then return true
}
return false
Q. How much space does this implementation need? (Time does not matter!)
P(I ,K0 = J,m)
P(I ,K1, m/2) P(K1,K0 = J, m/2)
P(I ,K2, m/4) P(K2,K1m/4)
. . . . . .
P(I ,Ki , m/2i) P(Ki ,Ki−1, m/2i)
∠ Required space: O(log(cp(n)) · p(n)) = O(p2(n)).
Q. Earlier we were assuming that there’s a unique J. Did we have to?
A. No, we could have just generated all possible (accepting) IDs and try all of them!
Pascal Bercher week 10: Other Complexity Classes Semester 1, 2023 10 / 11
PSPACE vs. NPSPACE (Savitch’s Theorem)
Relationship to Other Classes (Recap)
(Some of the) Classes covered so far
P ̸= EXPTIME (1)
P ⊆ NP ⊆ PSPACE ⊆ EXPTIME ⊆ NEXPTIME (2)
co-PSPACE = PSPACE = NPSPACE = co-NPSPACE (3)
Note:
∠ Relationships of the other co-classes for time are not shown.
∠ In (2), at least one inclusion must be proper (see (1)!), but we don’t know which!
∠ There are still many more classes,
both on the right ((N)EXPSPACE, DEXPTIME, . . . ),
in between, and
there are even classes of infinitely large hierarchies.
Pascal Bercher week 10: Other Complexity Classes Semester 1, 2023 11 / 11