The NP-hardness of finding a directed acyclic graph for regular resolution
type: Item
instance of: scholarly article
title: The NP-hardness of finding a directed acyclic graph for regular resolution
zbMATH Open document ID: 1145.03034
author: Samuel R. Buss
author: Jan Hoffmann
published in: Theoretical Computer Science
publication date: 2008-05-28T00:00:00Z
Mathematics Subject Classification ID: 03F20
Mathematics Subject Classification ID: 68Q17
zbMATH DE Number: 5279841
zbMATH Keywords: resolution
zbMATH Keywords: regular resolution
zbMATH Keywords: NP-completeness
zbMATH Keywords: directed acyclic graph
MaRDI profile type: Publication
full work available at URL: j.tcs.2008.01.039
OpenAlex ID: W2084517146
cites work: Minimum propositional proof length is NP-hard to linearly approximate
cites work: An exponential separation between regular and general resolution
cites work: Resolution Is Not Automatizable Unless W[P] Is Tractable
cites work: On the relative complexity of resolution refinements and cutting planes proof systems
cites work: The relative efficiency of propositional proof systems
cites work: On the complexity of regular resolution and the Davis-Putnam procedure
cites work: Regular Resolution Versus Unrestricted Resolution
cites work: Q4699307
cites work: Regular resolution lower bounds for the weak pigeonhole principle
cites work: Q3682461
cites work: Q4539605
cites work: Q5604434
DOI: 10.1016/J.TCS.2008.01.039
description: scientific article; zbMATH DE number 5279841