Computer Science – Discrete Mathematics
Scientific paper
2010-06-15
Computer Science
Discrete Mathematics
11 pages
Scientific paper
We determine the thresholds for the number of variables, number of clauses, number of clause intersection pairs and the maximum clause degree of a k-CNF formula that guarantees satisfiability under the assumption that every two clauses share at most $\alpha$ variables. More formally, we call these formulas $\alpha$-intersecting and define, for example, a threshold $\mu_i(k,\alpha)$ for the number of clause intersection pairs $i$, such that every $\alpha$-intersecting k-CNF formula in which at most $\mu_i(k,\alpha)$ pairs of clauses share a variable is satisfiable and there exists an unsatisfiable $\alpha$-intersecting k-CNF formula with $\mu_m(k,\alpha)$ such intersections. We provide a lower bound for these thresholds based on the Lovasz Local Lemma and a nearly matching upper bound by constructing an unsatisfiable k-CNF to show that $\mu_i(k,\alpha) = \tilde{\Theta}(2^{k(2+1/\alpha)})$. Similar thresholds are determined for the number of variables ($\mu_n = \tilde{\Theta}(2^{k/\alpha})$) and the number of clauses ($\mu_m = \tilde{\Theta}(2^{k(1+\frac{1}{\alpha})})$) (see [Scheder08] for an earlier but independent report on this threshold). Our upper bound construction gives a family of unsatisfiable formula that achieve all four thresholds simultaneously.
Chandrasekaran Karthekeyan
Goyal Navin
Haeupler Bernhard
No associations
LandOfFree
Satisfiability Thresholds for k-CNF Formula with Bounded Variable Intersections 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 Satisfiability Thresholds for k-CNF Formula with Bounded Variable Intersections, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Satisfiability Thresholds for k-CNF Formula with Bounded Variable Intersections will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-105338