The Normalized Autocorrelation Length of Random Max r -Sat Converges in Probability to (1-1/2^r)/r.
Daniel BerendYochai TwittoPublished in: SAT (2016)
Keyphrases
- higher order
- satisfiability problem
- probability functions
- probability distribution
- sat solving
- maximum number
- sat solvers
- search algorithm
- random sample
- information content
- orders of magnitude
- fixed length
- probability theory
- lower order
- total length
- optimal solution
- finite alphabet
- central limit theorem
- phase transition
- non stationary
- np hard