The Statistical Mechanics of k-Satisfaction
Kirkpatrick, Scott, Györgyi, Géza, Tishby, Naftali, Troyansky, Lidror
–Neural Information Processing Systems
The satisfiability of random CNF formulae with precisely k variables per clause ("k-SAT") is a popular testbed for the performance of search algorithms. Formulae have M clauses from N variables, randomly negated, keeping the ratio a M / N fixed.
Neural Information Processing Systems
Dec-31-1994
- Technology: