We summarise our results for the random $\epsilon$--1-in-3 satisfiability problem, where $\epsilon$ is a probability of negation of the variable. We employ both rigorous and heuristic methods to describe the SAT/UNSAT and Hard/Easy transitions.
A Hike in the phases of the 1-in-3 satisfiability / E. Maneva, T. Meltzer, J. Raymond, A. Sportiello, L. Zdeborová - In: Complex systems : lecture notes of the Les Houches Summer School 2006, session LXXXV, 3-28 July 2006 / [a cura di] J.P. Bouchaud, M. Mezard, J. Dalibard. - Amsterdam : Elsevier, 2007. - ISBN 978-0-444-53006-6. - pp. 491-498 (( Intervento presentato al 85. convegno Complex systems tenutosi a Les Houches nel 2006 [10.1016/S0924-8099(07)80022-9].
A Hike in the phases of the 1-in-3 satisfiability
A. SportielloPenultimo
;
2007
Abstract
We summarise our results for the random $\epsilon$--1-in-3 satisfiability problem, where $\epsilon$ is a probability of negation of the variable. We employ both rigorous and heuristic methods to describe the SAT/UNSAT and Hard/Easy transitions.
Pubblicazioni consigliate
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
