The Chvátal–Reed satisfiability threshold conjecture for random k-SAT
Statement
Let denote the random -SAT formula on variables with clauses, and let be the clause density. Write for a putative critical density.
Chvátal–Reed conjecture. For all there exists a value such that
This asserts a sharp satisfiability phase transition, separating formulas that are satisfiable with high probability from those that are unsatisfiable with high probability. The case was proved in the cited work, while the general problem was presented as an ongoing research effort 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 inSolve with an agent
Open the statement in a chat, with the problem and the ground rules already written into the prompt.