Access by Xinjiang University

Witness of unsatisfiability for a random 3-satisfiability formula

State Key Laboratory for Theoretical Physics, Institute of Theoretical Physics, Chinese Academy of Sciences, Beijing 100190, China

Department of Applied Physics, Aalto University, FI-00076 Aalto, Finland

ACCESS Linnaeus Center, KTH, Sweden, Department of Computational Biology, AlbaNova University Center, 10691 Stockholm, Sweden and Aalto University School of Science, FI-00076 Aalto, Finland

Department of Information and Computer Science, Aalto University, FI-00076 Aalto, Finland

PDF

Phys. Rev. E 87, 052807 – Published 20 May, 2013

DOI: https://doi.org/10.1103/PhysRevE.87.052807

Abstract

The random 3-satisfiability (3-SAT) problem is in the unsatisfiable (UNSAT) phase when the clause density $α$ exceeds a critical value $α_{s} \approx 4.267$ . Rigorously proving the unsatisfiability of a given large 3-SAT instance is, however, extremely difficult. In this paper we apply the mean-field theory of statistical physics to the unsatisfiability problem, and show that a reduction to 3-XORSAT, which permits the construction of a specific type of UNSAT witnesses (Feige-Kim-Ofek witnesses), is possible when the clause density $α > 19$ . We then construct Feige-Kim-Ofek witnesses for single 3-SAT instances through a simple random sampling algorithm and a focused local search algorithm. The random sampling algorithm works only when $α$ scales at least linearly with the variable number $N$ , but the focused local search algorithm works for clause density $α > c N^{b}$ with $b \approx 0.59$ and prefactor $c \approx 8$ . The exponent $b$ can be further decreased by enlarging the single parameter $S$ of the focused local search algorithm.

Article Text

References (27)

C. P. Gomes, H. Kautz, A. Sabharwal, and B. Selman, in Handbook of Knowledge Representation, edited by F. van Harmelen, V. Lifschitz, and B. Porter (Elsevier Science, Amsterdam, 2008), Chap. 2, pp. 89–134.
S. A. Cook, in Proceedings of the 3rd Annual ACM Symposium on Theory of Computing, edited by P. M. Lewis, M. J. Fischer, J. E. Hopcroft, A. L. Rosenberg, J. W. Thatcher, and P. R. Young (ACM, New York, 1971), pp. 151–158.
M. Garey and D. S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness (Freeman Publishing, San Francisco, CA, 1979).
P. Cheeseman, B. Kanefsky, and W. Taylor, in Proceedings of the 12th Int. Joint Conf. on Artificial Intelligence, Vol. 1 of IJCAI’91 (Morgan Kaufmann Publishers, Inc., San Francisco, CA, USA, 1991), pp. 163–169.
D. Mitchell, B. Selman, and H. Levesque, in Proceedings of the 10th National Conference on Artificial Intelligence (AAAI-92) (San Jose, CA, 1992), pp. 459–465.
S. Kirkpatrick and B. Selman, Science 264, 1297 (1994).
R. Monasson and R. Zecchina, Phys. Rev. Lett. 76, 3881 (1996).
M. Mézard, G. Parisi, and R. Zecchina, Science 297, 812 (2002).
M. Mézard and R. Zecchina, Phys. Rev. E 66, 056126 (2002).
F. Krzakala, A. Montanari, F. Ricci-Tersenghi, G. Semerjian, and L. Zdeborova, Proc. Natl. Acad. Sci. USA 104, 10318 (2007).
M. Alava, J. Ardelius, E. Aurell, P. Kaski, S. Krishnamurthy, P. Orponen, and S. Seitz, Proc. Natl. Acad. Sci. USA 105, 15253 (2008).
S. Mertens, M. Mézard, and R. Zecchina, Rand. Struct. Algorithms 28, 340 (2006).
A. Goerdt and M. Krivelevich, Lect. Notes Comput. Sci. 2010, 294 (2001).
U. Feige and E. Ofek, Lect. Notes Comput. Sci. 3142, 519 (2004).
A. Coja-Oghlan, A. Goerdt, and A. Lanka, Combinatorics, Probability and Computing 16, 5 (2007).
U. Feige, J. H. Kim, and E. Ofek, in Proceedings of 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS’06) (IEEE Computer Society, Los Alamitos, CA, USA, 2006), pp. 497–508.
C. Moore and S. Mertens, The Nature of Computation (Oxford University Press, Oxford, UK, 2011).
F. R. Kschischang, B. J. Frey, and H.-A. Loeliger, IEEE Trans. Inf. Theory 47, 498 (2001).
M. Mézard and G. Parisi, J. Stat. Phys. 111, 1 (2003).
M. Mézard and G. Parisi, Eur. Phys. J. B 20, 217 (2001).
M. Mézard and A. Montanari, Information, Physics, and Computation (Oxford University Press, New York, 2009).
A. Montanari, G. Parisi, and F. Ricci-Tersenghi, J. Phys. A: Math. Gen. 37, 2073 (2004).
M. Weigt and H. J. Zhou, Phys. Rev. E 74, 046110 (2006).
M. Mézard, F. Ricci-Tersenghi, and R. Zecchina, J. Stat. Phys. 111, 505 (2003).
J. Håstad, in Proceedings of the Twenty-Ninth Annual ACM Symposium on Theory of Computing, STOC '97 (ACM, New York, 1997), pp. 1–10.
H. J. Zhou and C. Wang, J. Stat. Phys. 148, 513 (2012).
J.-Q. Xiao and H. J. Zhou, J. Phys. A: Math. Theor. 44, 425001 (2011).

Physical Review E

Export citation

Export citation

Witness of unsatisfiability for a random 3-satisfiability formula

Abstract

Article Text

References (27)

Outline

Information

Filter

Filter

Article Lookup

Enter a citation