Space-Bounded Computation

Space-Bounded Computation

Lecture #10: Space-Bounded Computations — PSPACE

• Lecture Notes
• Exercise

Lecture #11: A PSPACE-Complete Problem

• Lecture Notes
• Exercise

Reading Exercise #8: Additional PSPACE-Complete Languages

• Assigned Reading

Lecture #12: L, NL, and Log-Space Reducibility

• Lecture Notes
• Supplemental Material
• Exercise

Lecture #13: NL = co-NL

• Lecture Notes
• Supplemental Material
• Exercise

Lecture #14: Alternation and the Polynomial Hierarchy

• Lecture Notes
• Supplemental Material
• Exercise

Assignment #2: Space-Bounded Computation and Complexity Classes

• Problems To Be Solved

cpsc 511/611 computer science faculty of science u of c

CPSC 511/611 intro to course deterministic computation nondeterministic computation space-bounded computation circuit computations randomzation, interaction and approximation structured models other topics assignments tests