Premiile Ad Astra
Revista Ad Astra
Biblioteca de știință
Cartea albă
Topul universităților
Who's who
Publicații
Teze și dizertații
Asociația Ad Astra
 
Comunicate
Știri
Evenimente
Oportunități de finanțare
 
Login
Înregistrare
 
>> English
 
   
 

Dimitris Achlioptas, Arthur Chtcherba, Gabriel Istrate and Cristopher Moore. The phase transition in 1-in-k SAT and NAE 3SAT. In 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

URL: http://portal.acm.org/citation.cfm?id=365411.365760&coll=portal&dl=ACM&type=series&idx=365411&part=Proceedings&WantType=Proceedings&title=Symposium%20on%20Discrete%20Algorithms&CFID=13842055&CFTOKEN=60725688

Adăugată pe site de Gabriel Istrate

Înapoi

   
© Ad Astra 2001-2013