Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > PHASE TRANSITIONS:
Reports tagged with phase transitions:
TR03-007 | 15th January 2003
Olivier Dubois, Yacine Boufkhad, Jacques Mandler

Typical random 3-SAT formulae and the satisfiability threshold

$k$-SAT is one of the best known among a wide class of random
constraint satisfaction problems believed to exhibit a threshold
phenomenon where the control parameter is the ratio, number of
constraints to number of variables. There has been a large amount of
work towards estimating ... more >>>




ISSN 1433-8092 | Imprint