sclv

With the new results showing that 3-SAT can be solved in subexponential time, let me explain the confusing ways theoretical computer scientists talk about "exponential time". There are two very different notions of exponential time in use: 1. The class E of problems solvable in 2^O(n) time, or equivalently O(2^(kn)) for some constant k, or O(c^n) for some constant c > 1. 2. The much broader class EXPTIME of problems solvable in O(2^(n^k)) time for some constant k. The second is a misnomer: it’s the exponential of a polynomial, not just an exponential. But it’s the one complexity theorists usually mean, because it’s closed under polynomial-time reductions. In particular, every problem in NP is in EXPTIME. Similarly, there are two notions of subexponential time: 1. 2^o(n): for every ε > 0, time O(2^(εn)), i.e. faster than O(c^n) for every constant c > 1. This one doesn’t have a standard class name. 2. The much smaller class SUBEXP: time O(2^(n^ε)) for every ε > 0. The results announced by OpenAI and Anthropic run in approximately 2^(n /√log n) time. That makes 3-SAT subexponential in the first, weaker sense. Proving 3-SAT is in SUBEXP would be a much bigger result. SUBEXP is closed under polynomial-time reductions and 3-SAT is NP-complete, so every problem in NP would then be solvable in subexponential time.