Solving the resolution-free SAT problem by submodel propagation in linear time
type: Item
instance of: scholarly article
title: Solving the resolution-free SAT problem by submodel propagation in linear time
zbMATH Open document ID: 1099.68101
author: Gábor Kusper
published in: Annals of Mathematics and Artificial Intelligence
publication date: 2005-05-13T00:00:00Z
Mathematics Subject Classification ID: 68T20
Mathematics Subject Classification ID: 68T27
zbMATH DE Number: 2168187
zbMATH Keywords: SAT
zbMATH Keywords: resolution-free SAT
zbMATH Keywords: submodel propagation
zbMATH Keywords: Unicorn-SAT
MaRDI profile type: Publication
full work available at URL: s10472-005-0423-7
OpenAlex ID: W4256704812
cites work: Recognizing disguised NR(1) instances of the satisfiability problem
cites work: A linear-time algorithm for testing the truth of certain quantified Boolean formulas
cites work: A Complexity Index for Satisfiability Problems
cites work: Recognition of \(q\)-Horn formulae in linear time
cites work: Extended Horn sets in propositional logic
cites work: A simplified NP-complete satisfiability problem
cites work: A hierarchy of tractable satisfiability problems
cites work: Linear-time algorithms for testing the satisfiability of propositional horn formulae
cites work: On the Complexity of Timetable and Multicommodity Flow Problems
cites work: Nested satisfiability
cites work: New methods for 3-SAT decision and worst-case analysis
cites work: A note on Dowling and Gallier's top-down algorithm for propositional Horn satisfiability
DOI: 10.1007/S10472-005-0423-7
Recommended article: Q4459906
Recommended article: Q3580786
Recommended article: On tackling the limits of resolution in SAT solving
Recommended article: Parameterized and subexponential-time complexity of satisfiability problems and applications
Recommended article: Parameterized and Subexponential-Time Complexity of Satisfiability Problems and Applications
Recommended article: Q4427902
Recommended article: Q3620438
Recommended article: Solving constraint satisfaction problems with SAT modulo theories
description: scientific article; zbMATH DE number 2168187