The satisfiability threshold conjecture for random k-SAT
Statement
Let be a uniformly random proper -SAT formula with variables and clauses, where each clause contains distinct variables, each possibly complemented, and clauses may be repeated. Write for this random formula, and let a property hold almost surely when its probability tends to as .
Satisfiability threshold conjecture. For each there exists a threshold density , such that for any positive , for all , is almost surely satisfiable, and for all , is almost surely unsatisfiable.
The conjecture asserts a sharp limiting satisfiability transition analogous to the known -SAT threshold. For large , 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 inSolve with an agent
Open the statement in a chat, with the problem and the ground rules already written into the prompt.