Linked from

The 42 pages that link to Computational complexity theory, each with the reason it gives.

• Turing machineRelated: Once computability is established, machine steps can be counted to compare efficiency.

• Formal languageRelated: Recognizing a language can be possible yet require prohibitive time or memory.

• Gaussian eliminationRelated: Dense elimination requires work that grows cubically with the number of unknowns.

• Economic calculation problemRelated: Modern computing revived questions about whether planning’s obstacle is computation as well as information.

• Computable functionRelated: Computability asks whether a procedure exists; complexity asks how costly it is.

• Sieve of EratosthenesRelated: The sieve’s running time and storage illustrate how algorithm costs depend on the limit.

• HeuristicRelated: Heuristics are often chosen when exact methods demand impractical computational resources.

• Minimum description lengthRelated: Finding optimal MDL models can be computationally difficult even when the criterion is clear.

• Leonid KantorovichRelated: Large planning problems exposed the computational limits of applying optimization at national scale.

• Description logicRelated: Reasoning costs help determine which description-logic constructors are practical.

• Discrete mathematicsRelated: Combinatorial growth and discrete problem structure determine computational difficulty.

• Automated reasoningRelated: Even decidable reasoning tasks may demand impractical time or memory.

• History of combinatoricsRelated: Modern combinatorics supplies tools for analyzing algorithms and the size of search spaces.

• Friends and strangers theoremRelated: Finding guaranteed Ramsey patterns can be computationally difficult even when existence is certain.

• War (card game)Related: Analyzing possible game histories raises questions about how much computation exact prediction requires.