Linked from

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

• Monte Carlo methodNarrower topic: It helps compare sampling cost with exact numerical methods as problem dimensions increase.

• 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.

• Computability theoryCompared with: Computability asks whether any algorithm exists; complexity asks how costly one is.

• Computer scienceBroader topic: It distinguishes problems by the cost of solving them, not merely by solvability.

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

• Randomized algorithmNarrower topic: Randomized algorithms define complexity classes according to probabilistic resource guarantees.

• Boolean satisfiability problemNarrower topic: SAT became a central benchmark for classifying the difficulty of decision problems.

• Kolmogorov complexityCompared with: It measures the cost of computation, not the length of the shortest program describing an output.

• Polynomial-time reductionNarrower topic: Polynomial-time reductions compare problem difficulty within this framework.

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

• Cook–Levin theoremNarrower topic: The theorem helped organize this field around reductions and complexity classes.

• 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.

• Undecidable problemCompared with: A decidable problem may be computationally expensive; undecidability means no complete algorithm exists.

• Shor's algorithmNarrower topic: Shor's polynomial-time result changed how factoring's complexity is assessed under quantum computation.

• Divide-and-conquer algorithmNarrower topic: Recurrence analysis connects individual divide-and-conquer algorithms to broader complexity bounds.

• Leonid LevinNarrower topic: Levin’s results helped shape this field’s account of intractability.

• Stephen CookNarrower topic: Cook’s foundational results helped establish this field as a rigorous theory.

• Automata theoryNarrower topic: Automata also serve as resource-bounded models for classifying efficient computation.

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

• Oracle Turing machineNarrower topic: Oracle access is used to compare resource-bounded computations under added information.

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

• Planar separator theoremNarrower topic: Separator bounds matter because they enable faster algorithms for graph problems.

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

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

• Theoretical computer scienceBroader topic: It classifies problems by the time and space algorithms need.

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

• Blum's speedup theoremNarrower topic: Blum's theorem is a foundational result about program resource costs.

• Andrew YaoNarrower topic: Yao’s lower bounds and complexity classes helped define this field’s central questions.

• BQPNarrower topic: BQP is one resource-bounded class in this broader framework.

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

• Stable roommates problemNarrower topic: It frames why polynomial-time solvability matters for large roommate instances.

• Blum axiomsNarrower topic: The axioms provide a machine-independent foundation for parts of this field.

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

• Hartmanis–Stearns conjectureNarrower topic: The conjecture is a central open question in this field.

• Linear speedup theoremNarrower topic: The theorem is a basic result about the robustness of time bounds.

• Model of computationNarrower topic: It compares models not only by what they compute, but by the cost of computation.

• Richard M. KarpNarrower topic: Karp’s classifications helped define how complexity theory compares problem difficulty.

• Turing's proofCompared with: Complexity asks how efficiently solvable problems can be computed; Turing’s proof concerns problems no algorithm solves at all.

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