Computational Complexity

(Up) | See also: Theory of Computation

Web resources

Computability and Complexity (Stanford Encyclopedia of Philosophy)

Descriptive Complexity

hierarchy theorems - Examples of collapsing hierarchies - Theoretical Computer Science Stack Exchange

lower bounds - Law of the Excluded Middle in complexity theory - Theoretical Computer Science Stack Exchange

Galactic algorithm - Wikipedia

Theory of Computing: An Open Access Electronic Journal in Theoretical Computer Science

P, NP, and beyond

turing machines - Do I need to consider instance restrictions when showing a language is in P? - Computer Science Stack Exchange

Cobham\'s thesis - Wikipedia

gr.group theory - Are there any computational problems in groups that are harder than P? - MathOverflow

cc.complexity theory - Subexponentially solvable hard graph problems - Theoretical Computer Science

cc.complexity theory - A category of NP-complete problems? - Theoretical Computer Science

P versus NP

P-versus-NP page

Computational Complexity: So You Think You Settled P verus NP

About P=NP and SAT « Gödel's Lost Letter and P=NP

PSPACE

Computational Complexity: A Simple PSPACE-Complete Problem

PR

computability theory - Inverse Ackermann - primitive recursive or not? - MathOverflow

Between mu- and primitive recursion - MathOverflow

computability theory - Is the collection of primitive recursive functions a lower set in the poset of computable functions? - MathOverflow

Papers

Why Philosophers Should Care About Computational Complexity (online @ www.scottaaronson.com, arxiv.org)

Protein folding is NP-hard (online @ www.gwern.net)

Complexity Hierarchies Beyond Elementary (online @ arxiv.org)

The Typed Lambda Calculus is not Elementary Recursive (online @ www.cs.cornell.edu)

Pure vs Impure Lisp (online @ dl.acm.org)

Books

Computers and Tractability (borrow @ archive.org)

Computational Complexity (Papadimitriou) (borrow with print disabilities @ archive.org)

Computational Complexity (Wagner and Wechsung) (borrow @ archive.org)