Complexity column Article Swipe

PDF

Related Concepts

Computational complexity theory Closure (psychology) Complexity class Class (philosophy) Column (typography) Mathematics Worst-case complexity Computer science Average-case complexity Theoretical computer science Discrete mathematics Algorithm Artificial intelligence Connection (principal bundle) Market economy Geometry Economics

Neil Immerman ·

YOU? · · 2018 · Open Access · · DOI: https://doi.org/10.1145/3292048.3292049 · OA: W4252985384

In 1975, Ladner proved that computational complexty is dense in the sense that if C 0 is strictly contained in C 1 , for any two complexity classes satisfying standard closure properties, then there is a complexity class C 0.5 strictly between them. However, naturally occuring algorithmic problems tend to be complete for one of a tiny stable of important complexity classes. This is often observed and leads to the great practical usefulness of the study of algorithms and complexity.