New paper breaks the 2^m barrier for restricted #SAT with faster algorithms and lower bounds
IgorCarron · x · 2026-10-15
A new arXiv paper, Solving Restricted Versions of #SAT Faster than 2^m: Algorithms and Lower Bounds (Sanjay Jain, Junqiang Peng, Frank Stephan, Mingyu Xiao), breaks a long-standing complexity barrier for #SAT counting.
Background: Under SETH, #SAT cannot be solved in O((2-ε)^n) or O((2-ε)^m) time, while exhaustive search and inclusion-exclusion give O(2^n) and O(2^m) respectively. The 2^n barrier was known to be breakable for constant clause size k or occurrence bound d, but the 2^m barrier stayed open.
Results:
- An O(2^(m(1-1/O(k)))) algorithm for #k-SAT, breaking the 2^m barrier for any constant k
- An O(2^(mω/3)) algorithm for #2-occ-SAT (which includes counting edge covers), with ω<2.3714 the matrix multiplication exponent
- Matching lower bounds are also established
More from Research
- DuplexJev Cuts Autoregressive Decoding for Voice Agents, Answering 80 Speech Decisions in 0.1s — adventists-ai · 2026-10-15
- LLM-to-Flow Distillation Adapts Scientific Generators to Natural-Language Discovery Goals — rbhar90 · 2026-10-15
- ETH's Uncertainty-Aware World Model Makes Offline RL Work on Real Robots — breadli428 · 2026-10-15
- 167,356 simulated shop-days: paper shows eval world design writes the model behavior it scores — liminal_bardo · 2026-10-15
- Multilingual NLP roadmap: researcher maps open problems from data selection to LID across 350+ languages — StellaLisy · 2026-10-15
- Beyond RAG: Injecting Tensor Memory Cartridges Into Layer-3 of a Frozen LLM — Nearby_Indication474 · 2026-10-15