Computation Complexity

From MGSA
Jump to: navigation, search
  • Define BPP. How does BPP relate to other complexity classes? (Vazirani)
  • What does NP = P(P(logn,1)) mean? (Vazirani)
  • Characterize {\rm NP}\cap{\rm coNP}.
  • Define the complexity classes PP and NP.
  • What is a nondeterministic Turing machine?
  • What is an NP-hard problem? What is an example?
  • Define PSPACE.
  • What is the relationship of NPSPACE and PSPACE?
  • Define LOGSPACE. What is strange about it?
  • Give containment relationships among the complexity classes named so far.
  • What is a search problem? An enumeration problem?
  • What is the complexity class associated to enumeration problems?

This page was originally derived from this TeX file.

Retrieved from "http://www.ocf.berkeley.edu/~mgsa/wiki/Computation_Complexity"
Personal tools