Phase Transition for Random Quantified XOR-Formulas
Creignou, N., Daude, H., Egly, U.
–arXiv.org Artificial Intelligence
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.
arXiv.org Artificial Intelligence
Oct-12-2011