ML Anthology

Phase Transition for Random Quantified XOR-Formulas

Nadia Creignou, Hervé Daudé, Uwe Egly
JAIR 2007 pp. 1-18
doi:10.1613/JAIR.2120 /jair/2007/creignou2007jair-phase/

Abstract

The QXOR-SAT problem is the quantified version of the satisfiability problem XOR-SAT in which the connective exclusive-or is used instead of the usual or. We study the phase transition associated with random QXOR-SAT instances. We give a description of this phase transition in the case of one alternation of quantifiers, thus performing an advanced practical and theoretical study on the phase transition of a quantified problem.

PDF JAIR Semantic Scholar

Cite

Text

Creignou et al. "Phase Transition for Random Quantified XOR-Formulas." Journal of Artificial Intelligence Research, 2007. doi:10.1613/JAIR.2120

Markdown

[Creignou et al. "Phase Transition for Random Quantified XOR-Formulas." Journal of Artificial Intelligence Research, 2007.](https://mlanthology.org/jair/2007/creignou2007jair-phase/) doi:10.1613/JAIR.2120

BibTeX

@article{creignou2007jair-phase,
  title     = {{Phase Transition for Random Quantified XOR-Formulas}},
  author    = {Creignou, Nadia and Daudé, Hervé and Egly, Uwe},
  journal   = {Journal of Artificial Intelligence Research},
  year      = {2007},
  pages     = {1-18},
  doi       = {10.1613/JAIR.2120},
  volume    = {29},
  url       = {https://mlanthology.org/jair/2007/creignou2007jair-phase/}
}