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.

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

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

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

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

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

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

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

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

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