New worst-case upper bounds for SAT
From MaRDI portal
Publication:1581847
DOI10.1023/A:1006340920104zbMath0960.03009OpenAlexW1564428908MaRDI QIDQ1581847
Publication date: 14 May 2001
Published in: Journal of Automated Reasoning (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1023/a:1006340920104
Analysis of algorithms and problem complexity (68Q25) Mechanization of proofs and logical operations (03B35) Complexity of computation (including implicit computational complexity) (03D15)
Related Items (22)
An improved upper bound for SAT ⋮ An improved exact algorithm for the domatic number problem ⋮ An Improved SAT Algorithm in Terms of Formula Length ⋮ An efficient fixed-parameter algorithm for 3-hitting set ⋮ Further improvements for SAT in terms of formula length ⋮ A tighter upper bound for random MAX \(2\)-SAT ⋮ Worst-case upper bounds for MAX-2-SAT with an application to MAX-CUT. ⋮ Worst-case study of local search for MAX-\(k\)-SAT. ⋮ Lean clause-sets: Generalizations of minimally unsatisfiable clause-sets ⋮ On the complexity of unique circuit SAT ⋮ Bounded list injective homomorphism for comparative analysis of protein-protein interaction graphs ⋮ Exact Algorithms for MAX-SAT ⋮ An Improved Algorithm for Detecting a Singleton Attractor in a Boolean Network Consisting of AND/OR Nodes ⋮ MAX SAT approximation beyond the limits of polynomial-time approximation ⋮ An improved algorithm for the \((n, 3)\)-MaxSAT problem: asking branchings to satisfy the clauses ⋮ An algorithm for exact satisfiability analysed with the number of clauses as parameter ⋮ Unnamed Item ⋮ Hard satisfiable instances for DPLL-type algorithms ⋮ A deterministic \((2-2/(k+1))^{n}\) algorithm for \(k\)-SAT based on local search. ⋮ An Empirical Study of MAX-2-SAT Phase Transitions ⋮ Improving exact algorithms for MAX-2-SAT ⋮ A fast algorithm for SAT in terms of formula length
This page was built for publication: New worst-case upper bounds for SAT
