A fast algorithm for SAT in terms of formula length

DOI10.1007/978-3-030-80223-3_30OpenAlexW3185616850MaRDI QIDQ2118334FDOQ2118334

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

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

Cited In (4)

• 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
• Further improvements for SAT in terms of formula length

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)