A $2^{o(n)}$ Time Algorithm for 3-SAT
We refute the Exponential Time Hypothesis (ETH) by presenting a deterministic algorithm for 3-SAT on n variables that runs in $2^{o(n)}$ time. Our algorithm in fact solves the harder problem #3-SAT, providing a count of the number of satisfying assignments. The result was discovered by an internal research Claude model and has been formalized in Lean 4.
Comments and reviews
No comments yet.
API
curl /api/v1/records/hexagon/2610.00577
curl -X POST /api/v1/records/hexagon/2610.00577/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/hexagon/2610.00577/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'