Inscriere cercetatori

Premii Ad Astra

premii Ad Astra

Asociația Ad Astra a anunțat câștigătorii Premiilor Ad Astra 2022: http://premii.ad-astra.ro/. Proiectul și-a propus identificarea și popularizarea modelelor de succes, a rezultatelor excepționale ale cercetătorilor români din țară și din afara ei.

Asociatia Ad Astra a cercetatorilor romani lanseaza BAZA DE DATE A CERCETATORILOR ROMANI DIN DIASPORA. Scopul acestei baze de date este aceea de a stimula colaborarea dintre cercetatorii romani de peste hotare dar si cu cercetatorii din Romania. Cercetatorii care doresc sa fie nominalizati in aceasta baza de date sunt rugati sa trimita un email la cristian.presura@gmail.com

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:

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