Computational Complexity Papers

Why Philosophers Should Care About Computational Complexity

• authors: Scott Aaronson
• date: 2011
• online @ www.scottaaronson.com
• online @ arxiv.org
• topics: Computational Complexity, Philosophy

Cobham's P-complete language is described in here.

Protein folding is NP-hard

• authors: Aviezri S. Fraenkel
• identifier: S0092-8240(05)80170-3
• date: 1993
• online @ www.gwern.net
• topics: Computational Complexity, Bioinformatics

.

Complexity Hierarchies Beyond Elementary

• authors: Sylvain Schmitz
• date: 2013
• online @ arxiv.org

.

The Typed Lambda Calculus is not Elementary Recursive

• authors: Richard Statman
• date: 1978
• online @ www.cs.cornell.edu
• topics: Lambda Calculus, Type Theory, Computational Complexity

.

Pure vs Impure Lisp

• authors: Nicholas Pippenger
• date: 1997
• online @ dl.acm.org
• topics: Computational Complexity, Functional Programming

.