Computational Complexity
(Up) | See also: Theory of Computation
Web resources
Computability and Complexity (Stanford Encyclopedia of Philosophy) ★★★
Examples of collapsing hierarchies ★
Law of the Excluded Middle in complexity theory ★
Galactic algorithm - Wikipedia
Theory of Computing: An Open Access Electronic Journal in Theoretical Computer Science ★ 💭
P, NP, and beyond
Do I need to consider instance restrictions when showing a language is in P? ★
Are there any computational problems in groups that are harder than P? ★
Subexponentially solvable hard graph problems
A category of NP-complete problems?
P versus NP
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
Inverse Ackermann - primitive recursive or not? ★
Between mu- and primitive recursion ★
Is the collection of primitive recursive functions a lower set in the poset of computable functions?
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)
(in Modal Logic) Topology, Connectedness, and Modal Logic (online @ www.dcs.bbk.ac.uk, web.archive.org) ★ 💭
(in Model Checking) Model Checking CTL is Almost Always Inherently Sequential 💭
Books
Computers and Tractability (borrow with print disabilities @ archive.org) 🏛️ 💭
Computational Complexity (Papadimitriou) (borrow with print disabilities @ archive.org) ★ 💭
Computational Complexity (Wagner and Wechsung) (borrow with print disabilities @ archive.org) ★ 💭
(in Linguistics) The Language Complexity Game (borrow @ archive.org) ★ 💭