A deterministic \((2-2/(k+1))^{n}\) algorithm for \(k\)-SAT based on local search.
From MaRDI portal
Publication:1853552
DOI10.1016/S0304-3975(01)00174-8zbMath1061.68071OpenAlexW2171680292WikidataQ57904544 ScholiaQ57904544MaRDI QIDQ1853552
Christos H. Papadimitriou, Prabhakar Raghavan, Edward A. Hirsch, Andreas Goerdt, Evgeny Dantsin, Jon M. Kleinberg, Uwe Schoening, Ravindran Kannan
Publication date: 21 January 2003
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/s0304-3975(01)00174-8
Related Items
An improved upper bound for SAT, Improved exact algorithms for MAX-SAT, Local Reductions, Sequential vector packing, Local reduction, Exploiting partial knowledge of satisfying assignments, Density condensation of Boolean formulas, Algorithms for four variants of the exact satisfiability problem, An efficient fixed-parameter algorithm for 3-hitting set, Strong ETH and resolution via games and the multiplicity of strategies, Derandomizing the HSSW algorithm for 3-SAT, A randomized algorithm for 3-SAT, Using small-scale quantum devices to solve algebraic equations, Worst-case upper bounds for MAX-2-SAT with an application to MAX-CUT., Worst-case study of local search for MAX-\(k\)-SAT., A new upper bound for \(( n , 3)\)-MAX-SAT, The parameterized complexity of \(k\)-flip local search for SAT and MAX SAT, Modelling the dynamics of stochastic local search on \(k\)-SAT, Bounded list injective homomorphism for comparative analysis of protein-protein interaction graphs, A note on the complexity of minimum dominating set, Chain, Generalization of Covering Code, and Deterministic Algorithm for k-SAT, Satisfiability Certificates Verifiable in Subexponential Time, An initial study of time complexity in infinite-domain constraint satisfaction, The complexity of Unique \(k\)-SAT: An isolation lemma for \(k\)-CNFs, Solving connected dominating set faster than \(2^n\), Exact Algorithms for MAX-SAT, Improved agreeing-gluing algorithm, Comparing the succinctness of monadic query languages over finite trees, Computing branchwidth via efficient triangulations and blocks, An improved deterministic local search algorithm for 3-SAT, The complexity of Boolean constraint satisfaction local search problems, UnitWalk: A new SAT solver that uses local search guided by unit clause elimination, Guided Search and a Faster Deterministic Algorithm for 3-SAT, Solving NP-Complete Problems with Quantum Search, A hybrid algorithm framework for small quantum computers with application to finding Hamiltonian cycles, Solving SAT for CNF Formulas with a One-Sided Restriction on Variable Occurrences, The Parameterized Complexity of k-Flip Local Search for SAT and MAX SAT, Using heuristics to find minimal unsatisfiable subformulas in satisfiability problems, On converting CNF to DNF, The resolution complexity of random graph \(k\)-colorability, An Empirical Study of MAX-2-SAT Phase Transitions, An improved local search algorithm for 3-SAT, Unrestricted vs restricted cut in a tableau method for Boolean circuits, Improving exact algorithms for MAX-2-SAT
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Number of models and satisfiability of sets of clauses
- Solving satisfiability in less than \(2^ n\) steps
- On the greedy algorithm for satisfiability
- Minimizing conflicts: A heuristic repair method for constraint satisfaction and scheduling problems
- New worst-case upper bounds for SAT
- New methods for 3-SAT decision and worst-case analysis
- SAT local search algorithms: Worst-case study
- An improved exponential-time algorithm for k -SAT
