polynomial time
A measure of algorithmic efficiency where the number of computation steps grows as a polynomial function of input size, considered tractable or 'doable' as opposed to exponential time.
As defined in 272 | Leslie Valiant on Learning and Educability in Computers and People
Other definitions
Running time that grows as a polynomial in input size, considered efficient in complexity theory.
Lex Fridman Podcast #503 - AI Crisis in Math
Where it comes up · 4
- 99 | Scott Aaronson on Complexity, Computation, and Quantum Gravity4 claims
- Lex Fridman Podcast #503 - AI Crisis in Math2 claims
- 272 | Leslie Valiant on Learning and Educability in Computers and People2 claims
- Sir Demis Hassabis on The Future of Knowledge | Institute for Advanced Study1 claim
Most important claims · 9 of 9Search all claims for “polynomial time” →
- The PAC (Probably Approximately Correct) model defines learning success as accurately predicting future examples from past examples, while requiring that the effort to reach that prediction is moderate (polynomial time) and that increased effort yields proportionally better accuracy, formalized as the error being a constant exponent of the effort.272 | Leslie Valiant on Learning and Educability in Computers and People
- Kontorovich argues that modern secure communication and e-commerce depend on the fact that no efficient classical algorithm for factoring large numbers is known, so a polynomial-time factoring algorithm would break most current encryption, although quantum computers pose a separate threat.Lex Fridman Podcast #503 - AI Crisis in Math
- The PAC model correctly anticipated modern large language models: it promised that the computation needed to learn well would be large but still polynomial-time and therefore doable, which is borne out by LLMs costing millions of dollars to train.272 | Leslie Valiant on Learning and Educability in Computers and People
- While Turing's notion of computability is invariant to the details of physics — classical or quantum, any number of spatial dimensions — the notion of efficient (polynomial-time) computability is more physics-dependent, and changing the laws from classical to quantum appears to enlarge what is computable in polynomial time, which is what led David Deutsch to invent quantum computing.99 | Scott Aaronson on Complexity, Computation, and Quantum Gravity
- The practical dividing line in complexity is whether a problem is solvable by an algorithm with polynomial scaling versus requiring exponential scaling; exponential growth becomes intractable so fast that even a 1000-digit problem would take longer than the age of the universe with every atom in the observable universe working in parallel, whereas polynomial algorithms can usually be improved with effort to low powers.99 | Scott Aaronson on Complexity, Computation, and Quantum Gravity
- A problem is in NP if, whenever its answer is yes, a solution can be exhibited and verified in polynomial time — like a completed jigsaw puzzle, prime factors that can be checked by multiplying, a solved Sudoku, or an optimization solution shown to a client — capturing the asymmetry between hard-to-solve but easy-to-check problems.99 | Scott Aaronson on Complexity, Computation, and Quantum Gravity
- Polynomial time (P) is contained in polynomial space (PSPACE), which is contained in exponential time, because a serial computer using N bits of memory can pass through at most 2-to-the-N states before halting or looping; we believe each containment is strict but have only proven that exponential time is strictly larger than polynomial time.99 | Scott Aaronson on Complexity, Computation, and Quantum Gravity
- Moitra explains P versus NP: problems whose solutions can be verified in polynomial time are NP, and the question is whether they can always be solved in polynomial time; the presumption is no, and most of modern cryptography relies on that presumption.Lex Fridman Podcast #503 - AI Crisis in Math
- P refers to problems that can be solved in polynomial time, while NP refers to problems that are not tractable to solve in reasonable time on a classical computer, though problems in NP have solutions that can be verified if you already have them.Sir Demis Hassabis on The Future of Knowledge | Institute for Advanced Study