Computational Complexity

Computability and Complexity (Stanford Encyclopedia of Philosophy)

• url: https://plato.stanford.edu/entries/computability/
• topics: Computational Complexity, Theory of Computation, Philosophy

.

Descriptive Complexity

• url: https://people.cs.umass.edu/~immerman/descriptive_complexity.html

.

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

• url: https://cstheory.stackexchange.com/questions/47333/examples-of-collapsing-hierarchies

.

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

• url: https://cstheory.stackexchange.com/questions/53305/law-of-the-excluded-middle-in-complexity-theory

.

Galactic algorithm - Wikipedia

• url: https://en.wikipedia.org/wiki/Galactic_algorithm

.

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

• url: http://theoryofcomputing.org/
• topics: Computational Complexity, Theory of Computation

.

P, NP, and beyond

• is-heading: true

.

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

• url: https://cs.stackexchange.com/questions/105692/do-i-need-to-consider-instance-restrictions-when-showing-a-language-is-in-p

.

Cobham\'s thesis - Wikipedia

• url: https://en.wikipedia.org/wiki/Cobham's_thesis

.

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

• url: https://mathoverflow.net/questions/321547/are-there-any-computational-problems-in-groups-that-are-harder-than-p

.

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

• url: https://cstheory.stackexchange.com/questions/3620/subexponentially-solvable-hard-graph-problems

.

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

• url: https://cstheory.stackexchange.com/questions/3074/a-category-of-np-complete-problems

.

P versus NP

• is-heading: true

.

P-versus-NP page

• url: https://www.win.tue.nl/~wscor/woeginger/P-versus-NP.htm

.

Computational Complexity: So You Think You Settled P verus NP

• url: http://blog.computationalcomplexity.org/2009/01/so-you-think-you-settled-p-verus-np.html

.

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

• url: http://rjlipton.wordpress.com/about/

.

PSPACE

• is-heading: true

.

Computational Complexity: A Simple PSPACE-Complete Problem

• url: https://blog.computationalcomplexity.org/2012/11/a-simple-pspace-complete-problem.html

.

PR

• is-heading: true

.

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

• url: https://mathoverflow.net/questions/76037/inverse-ackermann-primitive-recursive-or-not

.

Between mu- and primitive recursion - MathOverflow

• url: http://mathoverflow.net/questions/46350/between-mu-and-primitive-recursion

.

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

• url: https://mathoverflow.net/questions/364494/is-the-collection-of-primitive-recursive-functions-a-lower-set-in-the-poset-of-c

.