COMP 532 Propositional Proof Complexity

4 credits · Computer Science · Faculty of Science · Not scheduled for 2026–2027

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 a…

Prerequisite courses: COMP 330, COMP 360

Plan your whole degree in myDegree. Fit COMP 532 and everything it needs into a plan, term by term. Open myDegree

Source: McGill Course Catalogue. myDegree is an independent student project, not affiliated with McGill University.