A Threshold for a Polynomial Solution of #2SAT

• Autorzy: De Ita G. , Marcial-Romero J. R. , Hernandez J. A.
• Języki publikacji: EN

Abstrakty

EN

The #SAT problem is a classical #P-complete problem even for monotone, Horn and two conjunctive formulas (the last known as #2SAT). We present a novel branch and bound algorithm to solve the #2SAT problem exactly. Our procedure establishes a new threshold where #2SAT can be computed in polynomial time. We show that for any 2-CF formula F with n variables where #2SAT(F) . p(n), for some polynomial p, #2SAT(F) is computed in polynomial time. This is a new way to measure the degree of difficulty for solving #2SAT and, according to such measure our algorithm allows to determine a boundary between ‘hard’ and easy’ instances of the #2SAT problem.

Słowa kluczowe

EN

2SAT Problem; branch and bound algorithm; polynomial thresholds; efficient counting

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2011
• Tom: Vol. 113, nr 1
• Strony: 63--77
• Opis fizyczny: Bibliogr. 12 poz.

Twórcy

autor

De Ita G.

autor

Marcial-Romero J. R.

autor

Hernandez J. A.

• Computer Sciences Department, Benemerita Universidad Autónoma de Puebla, Mexico,

Bibliografia

• [1] Angelsmark O., Jonsson P., Improved Algorithms for Counting Solutions in Constraint Satisfaction Problems, Proc. 9th Int. Conf. on Principles and Practice of Constarinat Programming, (2003), pp 81-95.
• [2] Brueggemann T., Kern W., An improved deterministic local search algorithm for 3-SAT, Theoretical Computer Science, 329(1-3), (2004), pp.303-313.
• [3] De Ita G., Guillén C., Efficient Computation of the Degree of Belief for a Subclass of Two Conjunctive Forms, Jour. Inteligencia Artificial, 14(48), (2010), pp.15-27.
• [4] Gusfield D., Pitt L., A bounded approximation for the minimum cost 2-SAT problem, Algorithmica 8, (1992), pp. 103-117.
• [5] Iwama K., Tamaki S., Improved upper bounds for 3-SAT, Proc. of the 15th Annual ACM-SIAM Symp. On Discrete Algorithms, SODA, (2004), pp. 328-328.
• [6] Masaki Y., An Improved O(1.234m)-time deterministic algorithm for SAT, 16th ISAAC, LNCS No. 3827, (2005), pp. 644-653.
• [7] Roth D., On the hardness of approximate reasoning, Artificial Intelligence, 82, (1996), pp. 273-302.
• [8] Russ B., Randomized Algorithms: Approximation, Generation, and Counting, Distingished dissertations Springer, 2001.
• [9] Vilhelm D., Jonsson P., Wahlström M., Counting Satisfying Assignments in 2-SAT and 3-SAT, Proc. 8th Annual Int. Inf. Computing and Combinatorics, COCOON, (2002), pp 535-543.
• [10] Wahlström M., A Tighter Bound for Counting Max-Weight Solutions to 2SAT Instances, LNCS 5018, Springer-Verlag (2008), pp. 202-213.
• [11] Zheng L., Stuckey P.J., Improving SAT using 2SAT, Proc. 25th Australasian Comp. Sc. Conf., ACSC, (2002), pp. 331-340.
• [12] Zhou Junping, Yin Minghao, Zhou C., New Worts-Case Upper Bound for #2-SAT and #3-SAT with the Number of Clauses as the Parameter, Proc. of the AAAI, (2010), pp. 217-222