The threshold for random (1,2)-QSAT

Details The threshold for random (1,2)-QSAT The threshold for random (1,2)-QSAT

2009-07-06

arxiv.org/abs/0907.0937v1

Computer Science

Discrete Mathematics

20 pages. Preliminary, conference versions of this article appeared in SAT08 and SAT09

Scientific paper

The QSAT problem is the quantified version of the SAT problem. We show the existence of a threshold effect for the phase transition associated with the satisfiability of random quantified extended 2-CNF formulas. We consider boolean CNF formulas of the form $\forall X \exists Y \varphi(X,Y)$, where $X$ has $m$ variables, $Y$ has $n$ variables and each clause in $\varphi$ has one literal from $X$ and two from $Y$. For such formulas, we show that the threshold phenomenon is controlled by the ratio between the number of clauses and the number $n$ of existential variables. Then we give the exact location of the associated critical ratio $c^{*}$. Indeed, we prove that $c^{*}$ is a decreasing function of $ \alpha$, where $\alpha$ is the limiting value of $m / \log (n)$ when $n$ tends to infinity.

Affiliated with

Also associated with

No associations

Rating

The threshold for random (1,2)-QSAT does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with The threshold for random (1,2)-QSAT, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and The threshold for random (1,2)-QSAT will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-27322