exponential time
Resource usage that grows exponentially with problem size, quickly becoming intractable (e.g. longer than the age of the universe for modest sizes).
As defined in 99 | Scott Aaronson on Complexity, Computation, and Quantum Gravity
Where it comes up · 1
Most important claims · 3 of 3Search all claims for “exponential time” →
- Harlow and Hayden gave evidence that the quantum computation required to detect the relevant correlations in Hawking radiation — needed to provoke the firewall — would take a number of steps exponential in the number of qubits of the black hole, meaning roughly 2-to-the-(10-to-the-67) years, so you could not make a dent in the computation before the black hole itself evaporated, plausibly dissolving the paradox.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
- 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