TUBITAK Destekli Projelerden Çıkan Yayınlar Topluluğu
Published January 1, 2008 | Version v1
Conference paper Open

New results on the phase transition for random quantified Boolean formulas

Creators

  • 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

Description

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.

Files

bib-e750f4bf-59c0-459e-99ac-4c37d980cb1d.txt

Files (207 Bytes)

Name Size Download all
md5:ab2791ba6550cc539268ba20e81369ec
207 Bytes Preview Download