Creat membership Creat membership
Sign in

Forgot password?

Confirm
  • Forgot password?
    Sign Up
  • Confirm
    Sign In
Creat membership Creat membership
Sign in

Forgot password?

Confirm
  • Forgot password?
    Sign Up
  • Confirm
    Sign In
Collection

toTop

If you have any feedback, Please follow the official account to submit feedback.

Turn on your phone and scan

home > search >

A deterministic (2?2/(k+1))n algorithm for k-SAT based on local search

Author:
Evgeny Dantsin   Andreas Goerdt   Edward A Hirsch   Ravi Kannan   Jon Kleinberg   Christos Papadimitriou   Prabhakar Raghavan   Uwe Sch?ning  


Journal:
Theoretical Computer Science


Issue Date:
2002


Abstract(summary):

Local search is widely used for solving the propositional satisfiability problem. Papadimitriou (1991) showed that randomized local search solves 2-SAT in polynomial time. Recently, Schoning (1999) proved that a close algorithm for k-SAT takes time (2-2/k) n up to a polynomial factor. This is the best known worst-case upper bound for randomized 3-SAT algorithms (cf. also recent preprint by Schuler et al.). We describe a deterministic local search algorithm for k-SAT running in time (2-2/(k+1)) n up to a polynomial factor. The key point of our algorithm is the use of covering codes instead of random choice of initial assignments. Compared to other "weakly exponential" algorithms, our algorithm is technically quite simple. We also describe an improved version of local search. For 3-SAT the improved algorithm runs in time 1.481 n up to a polynomial factor. Our bounds are better than all previous bounds for deterministic k-SAT algorithms


Page:
69-83


Similar Literature

Submit Feedback

This function is a member function, members do not limit the number of downloads