Due to technical difficulties with the Course Catalogue, students should confirm course availability with Visual Schedule Builder (VSB) and Minerva. In cases where the Course Catalogue differs from these systems, VSB and Minerva should be considered the source of truth.

COMP 532. Propositional Proof Complexity.

Credits: 4
Offered by: Computer Science (Faculty of Science)
This course is not offered this catalogue year.

Description

Propositional proof systems and the complexity of NP. Introduction to various Boolean, Algebraic, and Semi-Algebraic proof systems and the complexity of their proofs. Techniques for upper and lower bounding complexity measures of proofs such as length and depth. Relationships between proof systems and algorithms in SAT solving and optimization. Connections between proof systems and other areas of complexity theory and theoretical computer science.
  • Prerequisites: COMP 330 or COMP 360

Most students use Visual Schedule Builder (VSB) to organize their schedules. VSB helps you plan class schedules, travel time, and more.

Launch Visual Schedule Builder
Back to top

We use cookies to help improve the usability of our websites.

What are you comfortable with?