New worst-case upper bounds for SAT
From MaRDI portal
DOI10.1023/A:1006340920104zbMATH Open0960.03009OpenAlexW1564428908MaRDI QIDQ1581847FDOQ1581847
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
Recommendations
Analysis of algorithms and problem complexity (68Q25) Mechanization of proofs and logical operations (03B35) Complexity of computation (including implicit computational complexity) (03D15)
Cited In (33)
- An algorithm for exact satisfiability analysed with the number of clauses as parameter
- Title not available (Why is that?)
- New worst-case upper bounds for SAT
- MAX SAT approximation beyond the limits of polynomial-time approximation
- An improved exact algorithm for the domatic number problem
- An efficient fixed-parameter algorithm for 3-hitting set
- Title not available (Why is that?)
- An exponential lower bound for the pure literal rule
- A fast algorithm for SAT in terms of formula length
- A deterministic \((2-2/(k+1))^{n}\) algorithm for \(k\)-SAT based on local search.
- Lean clause-sets: Generalizations of minimally unsatisfiable clause-sets
- Worst-case study of local search for MAX-\(k\)-SAT.
- Improving exact algorithms for MAX-2-SAT
- New width parameters for SAT and \#SAT
- Bounded list injective homomorphism for comparative analysis of protein-protein interaction graphs
- Worst-case upper bounds for MAX-2-SAT with an application to MAX-CUT.
- Title not available (Why is that?)
- Exact algorithms for MAX-SAT
- Theory and Applications of Satisfiability Testing
- An Improved SAT Algorithm in Terms of Formula Length
- An improved algorithm for the \((n, 3)\)-MaxSAT problem: asking branchings to satisfy the clauses
- Hard satisfiable instances for DPLL-type algorithms
- An Empirical Study of MAX-2-SAT Phase Transitions
- Algorithms for Sat and upper bounds on their complexity
- An Improved Algorithm for Detecting a Singleton Attractor in a Boolean Network Consisting of AND/OR Nodes
- A tighter upper bound for random MAX \(2\)-SAT
- Solving SAT by algorithm transform of Wu's method
- SAT-Based Horn Least Upper Bounds
- About some UP-based polynomial fragments of SAT
- An improved upper bound for SAT
- On the complexity of unique circuit SAT
- Further improvements for SAT in terms of formula length
- New Upper Bounds for Maximum Satisfiability
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)
