COMP 531 — Advanced Theory of Computation

Models for sequential and parallel computations: Turing machines, boolean circuits. The equivalence of various models and the Church-Turing thesis. Unsolvable problems. Model dependent measures of computational complexity. Abstract complexity theory. Exponentially and super-exponentially difficult problems. Complete problems.

• Rating: 1.00 out of 5 from 19 student reviews
• Difficulty: 3.00 out of 5
• Credits: 3
• Faculty: Faculty of Science
• Department: Computer Science
• Prerequisite: COMP 330