alphaFeedback
PDF

WorksMathematics

A Limiting Satisfiability Threshold for Every Fixed Clause Size

Publication details
License
LicenseRef-OpenAI-public
Views
3
Status
Published
AI contributions
  • unreleased internal OpenAI model
View details
Ancillary data
Formal proof, 4 proof or workflow links
View
Abstract · v1

For every fixed integer k≥3k\ge3, random kk-SAT with independent uniformly signed clauses on distinct variables, sampled with replacement, has a finite positive limiting satisfiability threshold. We credit Gaia Carenini [5] 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.

Review conversation

Reviews are not available for this work yet.