Complexity Theory Supervision Work

Supervision 1
 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 nondeterministic
Turing machines. Are nondeterministic Turing machines more powerful?

Supervision 2
 2002 V 12  reductions and graph problems
 2005 V 10  nondeterministic Turing machines and NPcomplete problems
 2006 VI 12  black boxes and reductions

Supervision 3
 2004 VI 12  oneway functions, reachability and satisfiability
 2002 VI 12  time hierarchy theorem
 2007 V 12  proving NPcompleteness
Last modified: Sun Sep 11 17:47:31 MDT 2011