A fast algorithm for SAT in terms of formula length

DOI10.1007/978-3-030-80223-3_30MaRDI QIDQ2118334zbMATH OpenOpenAlexFDO

Authors Junqiang Peng, Mingyu Xiao

Publication date 22 March 2022

Full work available at URL https://arxiv.org/abs/2105.06131

zbMATH Keywords

measure-and-conquersatisfiabilityparameterized algorithms

Mathematics Subject Classification ID

Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Analysis of algorithms and problem complexity (68Q25) Computational aspects of satisfiability (68R07)

Cites work

• scientific article; zbMATH DE number 1303594 (Why is no real title available?)
• scientific article; zbMATH DE number 1113991 (Why is no real title available?)
• scientific article; zbMATH DE number 3803174 (Why is no real title available?)
• scientific article; zbMATH DE number 5493266 (Why is no real title available?)
• A Computing Procedure for Quantification Theory
• A measure \& conquer approach for the analysis of exact algorithms
• A satisfiability tester for non-clausal propositional calculus
• Algorithms and Computation
• Algorithms – ESA 2005
• An Improved SAT Algorithm in Terms of Formula Length
• Chain, generalization of covering code, and deterministic algorithm for \(k\)-SAT
• Exact exponential algorithms.
• New worst-case upper bounds for SAT
• On the complexity of \(k\)-SAT
• The complexity of theorem-proving procedures
• Theory and Applications of Satisfiability Testing

Cited in

(4)

• Further improvements for SAT in terms of formula length
• SAT-Based Formula Simplification
• Can rare SAT formulae be easily recognized? On the efficiency of message-passing algorithms forK-SAT at large clause-to-variable ratios
• STACS 2004

This page was built for publication: A fast algorithm for SAT in terms of formula length

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