Sökning: onr:"swepub:oai:DiVA.org:kth-124461" >
Witness of unsatisf...
Witness of unsatisfiability for a random 3-satisfiability formula
-
Wu, Lu-Lu (författare)
-
Zhou, Hai-Jun (författare)
-
Alava, Mikko (författare)
-
visa fler...
-
- Aurell, Erik (författare)
- KTH,Beräkningsbiologi, CB,ACCESS Linnaeus Centre
-
Orponen, Pekka (författare)
-
visa färre...
-
(creator_code:org_t)
- 2013
- 2013
- Engelska.
-
Ingår i: Physical Review E. Statistical, Nonlinear, and Soft Matter Physics. - 1539-3755 .- 1550-2376. ; 87:5, s. 052807-
- Relaterad länk:
-
https://urn.kb.se/re...
-
visa fler...
-
https://doi.org/10.1...
-
visa färre...
Abstract
Ämnesord
Stäng
- The random 3-satisfiability (3-SAT) problem is in the unsatisfiable (UNSAT) phase when the clause density alpha exceeds a critical value alpha(s) approximate to 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 alpha > 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 a scales at least linearly with the variable number N, but the focused local search algorithm works for clause density alpha > cN(b) with b approximate to 0.59 and prefactor c approximate to 8. The exponent b can be further decreased by enlarging the single parameter S of the focused local search algorithm.
Ämnesord
- NATURVETENSKAP -- Fysik (hsv//swe)
- NATURAL SCIENCES -- Physical Sciences (hsv//eng)
Publikations- och innehållstyp
- ref (ämneskategori)
- art (ämneskategori)
Hitta via bibliotek
Till lärosätets databas