On finding short resolution refutations and small unsatisfiable subsets
type: Item
instance of: scholarly article
title: On finding short resolution refutations and small unsatisfiable subsets
zbMATH Open document ID: 1087.03035
author: Michael R. Fellows
author: Stefan Szeider
author: Graham Wrightson
published in: Theoretical Computer Science
publication date: 2006-04-06T00:00:00Z
Mathematics Subject Classification ID: 03F20
Mathematics Subject Classification ID: 03D15
Mathematics Subject Classification ID: 68Q15
Mathematics Subject Classification ID: 68Q25
zbMATH DE Number: 5017472
zbMATH Keywords: resolution complexity
zbMATH Keywords: parameterized complexity
zbMATH Keywords: \(\text{W}[1]\)-completeness
zbMATH Keywords: bounded local treewidth
zbMATH Keywords: planar formulas
MaRDI profile type: Publication
full work available at URL: j.tcs.2005.10.005
OpenAlex ID: W2171456022
cites work: Minimal non-two-colorable hypergraphs and minimal unsatisfiable formulas
cites work: Minimum propositional proof length is NP-hard to linearly approximate
cites work: Resolution Is Not Automatizable Unless W[P] Is Tractable
cites work: Q4790380
cites work: A partial k-arboretum of graphs with bounded treewidth
cites work: Q4718423
cites work: On the fixed parameter complexity of graph enumeration problems definable in monadic second-order logic
cites work: Q4393480
cites work: Q4255575
cites work: Deciding first-order properties of locally tree-decomposable structures
cites work: The intractability of resolution
cites work: Q4699307
cites work: A special planar satisfiability problem and a consequence of its NP- completeness
cites work: Elements of finite model theory.
cites work: Planar Formulae and Their Uses
cites work: On the complexity of database queries
cites work: Theory and Applications of Satisfiability Testing
cites work: A simplified NP-complete satisfiability problem
cites work: Q5593816
Wikidata QID: Q57359981
DBLP publication ID: journals/tcs/FellowsSW06
DOI: 10.1016/J.TCS.2005.10.005
description: scientific article; zbMATH DE number 5017472