Linked from

The 9 pages that link to Polynomial time, each with the reason it gives.

• Computational complexity theoryRelated: It is the standard formal benchmark for efficient computation.

• P versus NP problemRelated: Polynomial time defines efficiency for both solving and verification.

• Time complexityRelated: Polynomial growth is a central benchmark for tractable computation.

• Polynomial-time reductionRelated: Its growth-rate bound defines the allowed cost of the transformation.

• Approximation algorithmRelated: Efficiency usually means polynomial running time in approximation-algorithm theory.

• Cook–Levin theoremRelated: Both the reduction and the verification fit this resource bound.

• NP-hardnessRelated: The defining reductions must be computable within this time bound.

• Oracle Turing machineRelated: Complexity classes with oracles often restrict total running time to this bound.

• Hartmanis–Stearns conjectureNarrower topic: It defines the efficiency threshold shared by P and NP.