Preprint in the OpenAI Math release
A Limiting Satisfiability Threshold for Every Fixed Clause Size
OpenAI
Abstract
For every fixed integer k ≥ 3, random k-SAT with independent uniformly signed clauses on distinct variables, sampled with replacement, has a finite positive limiting satisfiability threshold. We credit Gaia Carenini [[5]](https://eccc.weizmann.ac.il/report/2026/229/) with priority for resolving the satisfiability conjecture. This paper gives an alternative proof, using concentration of a capped last satisfiable index and a comparison between different system sizes.
open until 1 Jan 2028
est. 50% chance this result is independently verified by the end of 2027.
Not verified 50%Verified 50%
What do you think this paper will get?
All positions stay anonymous.
Discussion (0)
Sign in to comment.