Ryan Williams' stated bound: subexponential 3SAT at exp(n/(log n)^{1/2+o(1)}), not polynomial
AIFlow_ML · x · 2026-10-27
In the discussion around the claimed ETH disproof, AIFlowML quotes Ryan Williams' precise bound: the new 3SAT algorithm runs in about exp(n/(log n)^{1/2+o(1)}) time on n variables — asymptotically below every 2^(cn) algorithm, but not polynomial, and the paper itself states it does not make all of NP subexponential. A useful scoping of what the "ETH disproven" claim actually delivers.
More from Research
- Insilico's AI-designed Pan-TEAD inhibitor ISM6331 hits 40% ORR in mesothelioma Phase 1 — rand_longevity · 2026-10-27
- RL doesn't just reward thinking longer—it incentives parallel agent swarms — rosstaylor90 · 2026-10-27
- Reversed audio has identical magnitude spectra: the time-frequency resolution tradeoff — techNmak · 2026-10-27
- Researcher argues DoM steering is no more transparent than gradient-based vector selection — johnhewtt · 2026-10-27
- DoM steering working at a localized layer doesn't prove localization is correct — johnhewtt · 2026-10-27
- MPI's Alien Recombination method finds concept blends beyond human cognitive reach — profjamesevans · 2026-10-27