Complexity Theory Supervision Work
- Comment on the relationship between this course and last term's Computation Theory course.
- Suppose that you have (i) a propositional formula containing n propositional letters,
and (ii) a program for working out whether a given truth assignment to those propositional
letters satisfies the formula. Describe a naive algorithm for testing whether the formula
is satisfiable. Can you think of a better algorithm?
- Briefly define and discuss the notions of time and space complexity.
- Describe the difference between deterministic and non-deterministic
Turing machines. Are non-deterministic Turing machines more powerful?
- 2002 V 12 - reductions and graph problems
- 2005 V 10 - non-deterministic Turing machines and NP-complete problems
- 2006 VI 12 - black boxes and reductions
- 2004 VI 12 - one-way functions, reachability and satisfiability
- 2002 VI 12 - time hierarchy theorem
- 2007 V 12 - proving NP-completeness
Last modified: Sun Sep 11 17:47:31 MDT 2011