Commentary by Chris Pressey

This work is distributed under a CC-BY-ND-4.0 license, with the following explicit exception: the ratings may be freely used for any purpose with no limitations.

Computational Complexity

Computers and Tractability

• rating: classic

The classic work presenting a compilation of many NP-complete problems.

Computational Complexity (Papadimitriou)

• rating: 1

Really quite good book on the subject. One memory I have from it is the economical definition of Turing machines; they're defined as a 4-tuple (in contrast to other author's definitions using, say, a 7-tuple); another is the discussion early on of what metrics can be used for complexity and what can't, and how one can define pathological metrics.

Computational Complexity (Wagner and Wechsung)

• rating: TODO

Gosh, this is incredibly heavy. It's hard to imagine any individual ever owning this book; I can only imagine it belonging to a university library. That sort of book.

Why Philosophers Should Care About Computational Complexity

• rating: 3

There's some good stuff here, but it's not all good stuff.

Mainly, this is where I discovered Cobham's P-complete formulation. It comes via another paper via another paper though, so it should really be described there.

There are a few other interesting things in this essay though. The "waterfall as computation" example, for example.

Protein folding is NP-hard

• rating: 1

.

Complexity Hierarchies Beyond Elementary

• rating: TODO

I need to skim this and take some notes.

The Typed Lambda Calculus is not Elementary Recursive

• rating: 1

.

Computability and Complexity (Stanford Encyclopedia of Philosophy)

• rating: 3

.

Descriptive Complexity

• rating: 2

.

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

• rating: 1

Articles are CC-BY-something licensed.

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

• rating: 1

.

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

• rating: 1

.

Galactic algorithm - Wikipedia

• rating: TODO

.

P, NP, and beyond

• rating: TODO

.

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

• rating: 1

.

Cobham\'s thesis - Wikipedia

• rating: TODO

.

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

• rating: 1

.

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

• rating: 0

.

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

• rating: 0

.

P versus NP

• rating: TODO

.

P-versus-NP page

• rating: 1

.

Computational Complexity: So You Think You Settled P verus NP

• rating: 3

.

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

• rating: 1

.

PSPACE

• rating: TODO

.

Computational Complexity: A Simple PSPACE-Complete Problem

• rating: 3

.

PR

• rating: TODO

.

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

• rating: 1

.

Between mu- and primitive recursion - MathOverflow

• rating: 1

.

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

• rating: 0

.