3-SAT Faster and Simpler---Unique-SAT Bounds for PPSZ Hold in General
From MaRDI portal
Publication:5494936
DOI10.1137/120868177zbMath1297.68216arXiv1103.2165OpenAlexW2180459618MaRDI QIDQ5494936
Publication date: 30 July 2014
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1103.2165
Analysis of algorithms and problem complexity (68Q25) Combinatorics in computer science (68R05) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Randomized algorithms (68W20)
Related Items (11)
On the Equivalence among Problems of Bounded Width ⋮ Strong partial clones and the time complexity of SAT problems ⋮ Matching cut: kernelization, single-exponential time FPT, and exact exponential algorithms ⋮ Chain, Generalization of Covering Code, and Deterministic Algorithm for k-SAT ⋮ Solving and sampling with many solutions ⋮ Super strong ETH is true for PPSZ with small resolution width ⋮ Time Complexity of Constraint Satisfaction via Universal Algebra ⋮ Solving and sampling with many solutions: Satisfiability and other hard problems ⋮ On Super Strong ETH ⋮ Moderate exponential-time algorithms for scheduling problems ⋮ Walksat Stalls Well Below Satisfiability
This page was built for publication: 3-SAT Faster and Simpler---Unique-SAT Bounds for PPSZ Hold in General
