Yayınlanmış 1 Ocak 2008
| Sürüm v1
Konferans bildirisi
Açık
New results on the phase transition for random quantified Boolean formulas
Oluşturanlar
- 1. Univ Aix Marseille, Lab Informat Fondamentale, F-13288 Marseille, France
- 2. Univ Aix Marseille, Lab Anal, Topologie Probabilites, F-13453 Marseille, France
- 3. Vienna Univ Technol, Inst Informatsyst, A-1040 Vienna, Austria
- 4. Univ Paris, Dept Math, F-91405 Orsay, France
Açıklama
The QSAT problem is the quantified version of the satisfiability problem SAT. We study the phase transition associated with random QSAT instances. We focus on a certain subclass of closed quantified Boolean formulas that can be seen as quantified extended 2-CNF formulas. The evaluation problem for this class is coNP-complete. We carry out an advanced practical and theoretical study, which illuminates the influence of the different parameters used to define random quantified instances.
Dosyalar
bib-e750f4bf-59c0-459e-99ac-4c37d980cb1d.txt
Dosyalar
(207 Bytes)
| Ad | Boyut | Hepisini indir |
|---|---|---|
|
md5:ab2791ba6550cc539268ba20e81369ec
|
207 Bytes | Ön İzleme İndir |