New worst-case upper bounds for SAT

DOI10.1023/A:1006340920104MaRDI QIDQ1581847zbMATH OpenOpenAlexFDO

Authors Edward A. Hirsch

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

zbMATH Keywords

algorithmssatisfiability of a propositional formulatransformation ruleworst-case upper bounds

Mathematics Subject Classification ID

Mechanization of proofs and logical operations (03B35) Complexity of computation (including implicit computational complexity) (03D15) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• New worst-case upper bounds for SAT
• Algorithms for Sat and upper bounds on their complexity
• scientific article; zbMATH DE number 1303594
• scientific article; zbMATH DE number 956865
• New Upper Bounds for Maximum Satisfiability

Cited in

(34)

• An algorithm for exact satisfiability analysed with the number of clauses as parameter
• An exponential lower bound for the pure literal rule
• 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
• A deterministic \((2-2/(k+1))^{n}\) algorithm for \(k\)-SAT based on local search.
• A tighter upper bound for random MAX \(2\)-SAT
• Solving SAT by algorithm transform of Wu's method
• An improved algorithm for the (n, 3)-MaxSAT problem: asking branchings to satisfy the clauses
• A fast algorithm for SAT in terms of formula length
• On the complexity of unique circuit SAT
• New width parameters for SAT and \#SAT
• Algorithms for Sat and upper bounds on their complexity
• Hard satisfiable instances for DPLL-type algorithms
• New worst-case upper bounds for SAT
• An Improved SAT Algorithm in Terms of Formula Length
• An Empirical Study of MAX-2-SAT Phase Transitions
• SAT-Based Horn Least Upper Bounds
• An Improved Algorithm for Detecting a Singleton Attractor in a Boolean Network Consisting of AND/OR Nodes
• scientific article; zbMATH DE number 1303594 (Why is no real title available?)
• scientific article; zbMATH DE number 1113996 (Why is no real title available?)
• New Upper Bounds for Maximum Satisfiability
• Exact algorithms for MAX-SAT
• About some UP-based polynomial fragments of SAT
• scientific article; zbMATH DE number 7310227 (Why is no real title available?)
• scientific article; zbMATH DE number 2187722 (Why is no real title available?)
• Theory and Applications of Satisfiability Testing
• MAX SAT approximation beyond the limits of polynomial-time approximation
• Further improvements for SAT in terms of formula length
• Improving exact algorithms for MAX-2-SAT
• An improved upper bound for SAT
• An improved exact algorithm for the domatic number problem
• An efficient fixed-parameter algorithm for 3-hitting set
• Bounded list injective homomorphism for comparative analysis of protein-protein interaction graphs

This page was built for publication: New worst-case upper bounds for SAT

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1581847)