Scopul nostru este sprijinirea şi promovarea cercetării ştiinţifice şi facilitarea comunicării între cercetătorii români din întreaga lume.
Domenii publicaţii > Ştiinţe informatice + Tipuri publicaţii > Articol în volumul unei conferinţe
Autori: Dimitris Achlioptas, Arthur Chtcherba, Gabriel Istrate and Cristopher Moore
Editorial: Proceedings of the Twelfth ACM-SIAM Symposium on Discrete Algorithms (SODA'01), Washington, DC, USA, 2001.
Rezumat:
We determine the precise value of the satisfiability threshold of random 1-in-k SAT. The analysis essentially shows that this (NP-complete) problem
is in the same universality class as the polynomial time computable problem 2SAT, and has a second-order phase transition.
We also obtain rigorous lower and upper bounds, as well an experimental estimate of the location of the phase transition in random NAE 3SAT.
Cuvinte cheie: satisfiability, sharp thresholds, probabilistic analysis