Inscriere cercetatori

Daca aveti cont Ad Astra si de Facebook, intrati pe pagina de profil pentru a da dreptul sa va logati pe site doar cu acest buton.

Site nou !

Daca nu va puteti recupera parola (sau aveti alte probleme), scrieti-ne la pagina de contact. Situl vechi se gaseste la adresa old.ad-astra.ro

Facebook

The phase transition in 1-in-k SAT and NAE 3SAT

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:

Want create site? Find Free WordPress Themes and plugins.

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.

Did you find apk for android? You can find new Free Android Games and apps.

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