A probabilistic algorithm for \(k\)-SAT based on limited local search and restart
From MaRDI portal
Publication:1348911
DOI10.1007/s00453-001-0094-7zbMath1050.68049OpenAlexW2082757215MaRDI QIDQ1348911
Publication date: 21 May 2002
Published in: Algorithmica (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00453-001-0094-7
Analysis of algorithms and problem complexity (68Q25) Searching and sorting (68P10) Randomized algorithms (68W20)
Related Items (21)
Sequential vector packing ⋮ Performances of pure random walk algorithms on constraint satisfaction problems with growing domains ⋮ Algorithms for four variants of the exact satisfiability problem ⋮ Quantum Walk Based Search Algorithms ⋮ Towards NP-P via proof complexity and search ⋮ A randomized algorithm for 3-SAT ⋮ Analysis of local search landscapes for \(k\)-SAT instances ⋮ On the exact complexity of evaluating quantified \(k\)-\textsc{cnf} ⋮ An exact exponential time algorithm for counting bipartite cliques ⋮ An exact algorithm for the Boolean connectivity problem for \(k\)-CNF ⋮ New exact algorithms for the 2-constraint satisfaction problem ⋮ Solving SCS for bounded length strings in fewer than \(2^n\) steps ⋮ Absorbing random walks and the NAE2SAT problem ⋮ An initial study of time complexity in infinite-domain constraint satisfaction ⋮ The complexity of Unique \(k\)-SAT: An isolation lemma for \(k\)-CNFs ⋮ Improved agreeing-gluing algorithm ⋮ An improved deterministic local search algorithm for 3-SAT ⋮ On the complexities of selected satisfiability and equivalence queries over Boolean formulas and inclusion queries over hulls ⋮ Solving and sampling with many solutions: Satisfiability and other hard problems ⋮ On converting CNF to DNF ⋮ An improved local search algorithm for 3-SAT
This page was built for publication: A probabilistic algorithm for \(k\)-SAT based on limited local search and restart
