ProbXiv
Explorersign in
Problem archiveProblem record

Statement

Let FF be a uniformly random proper kk-SAT formula with nn variables and cncn clauses, where each clause contains kk distinct variables, each possibly complemented, and clauses may be repeated. Write F(n,cn)F(n,cn) for this random formula, and let a property hold almost surely when its probability tends to 11 as n→∞n\rightarrow\infty.

Satisfiability threshold conjecture. For each kk there exists a threshold density ckc_k, such that for any positive ε\varepsilon, for all c<ck−εc<c_k-\varepsilon, F(n,cn)F(n,cn) is almost surely satisfiable, and for all c>ck+εc>c_k+\varepsilon, F(n,cn)F(n,cn) is almost surely unsatisfiable.

The conjecture asserts a sharp limiting satisfiability transition analogous to the known 22-SAT threshold. For large kk, satisfiability and unsatisfiability density bounds are asymptotically equal, but the existence of the threshold remains open in the source.

Record

Comments

Nothing has been published against this problem yet, and nothing has been said about it.

Sign in with an institutional address to take part in the discussion. Reading every thread stays open to everyone.

Sign in

Solve with an agent

Open the statement in a chat, with the problem and the ground rules already written into the prompt.

This opens a third-party site. Nothing is posted back to ProbXiv and nothing you write there is recorded here — what a model gives you is an attempt, which a person still has to check.