Differences
This shows you the differences between two versions of the page.
| Both sides previous revision Previous revision Next revision | Previous revision | ||
|
sav08:computational_complexity [2008/02/21 10:45] vkuncak |
sav08:computational_complexity [2010/02/22 01:13] vkuncak |
||
|---|---|---|---|
| Line 9: | Line 9: | ||
| * Deterministic and non-deterministic complexity | * Deterministic and non-deterministic complexity | ||
| * Undecidable and Enumerable (Semidecidable) problems | * Undecidable and Enumerable (Semidecidable) problems | ||
| + | |||
| + | Some important classes of problems: | ||
| + | * P, NP, coNP, PSPACE, EXPTIME, NEXPTIME, elementary | ||
| + | |||
| + | Ackerman's function | ||
| ===== More Information ===== | ===== More Information ===== | ||
| + | * [[http://infowww.epfl.ch/imoniteur_ISAP/!itffichecours.htm?ww_i_matiere=238861988&ww_x_anneeAcad=2009-2010&ww_i_section=2139068&ww_c_langue=en|Theory of Computation Course]] | ||
| + | * [[Calculus of Computation Textbook]], Section 2.6 (Decidability and Complexity) | ||
| * [[:Gallier Logic Book]], Section 3.3.5 | * [[:Gallier Logic Book]], Section 3.3.5 | ||
| * [[Theory of Computation Courses and Books]] | * [[Theory of Computation Courses and Books]] | ||
| * [[http://www.cs.princeton.edu/theory/complexity/|Complexity Theory: A Modern Approach]], Chapter on [[http://www.cs.princeton.edu/theory/complexity/NPchap.pdf|NP and NP completeness]] | * [[http://www.cs.princeton.edu/theory/complexity/|Complexity Theory: A Modern Approach]], Chapter on [[http://www.cs.princeton.edu/theory/complexity/NPchap.pdf|NP and NP completeness]] | ||