Nondeterministic Computation

Nondeterministic Computation

Lecture #6: Introduction to Nondeterministic Computation

• Lecture Notes
• Supplemental Material
• Exercise

Reading Exercise #5: Encoding Schemes — When They Don’t Matter (and When They Do)

• Assigned Reading

Lecture #7: The Cook-Levin Theorem

• Lecture Notes
• Supplemental Material
• Exercise

Lecture #8: NP-Completeness — Classical Reductions

• Lecture Notes
• Supplemental Material
• Exercise

Lecture #9: More about Nondeterministic Computation

• Lecture Notes
• Supplemental Material
• Exercise

Reading Exercise #6: Nondeterministic Universal Turing Machines and a Better Time Hierarchy Theorem

• Assigned Reading

Reading Exercise #7: Relativized Complexity Classes and the Relationship Between P^L and NP^L

• Assigned Reading

Assignment #2: NP-Completeness

• 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