Near optimal seperation of tree-like and general resolution
type: Item
instance of: scholarly article
title: Near optimal seperation of tree-like and general resolution
zbMATH Open document ID: 1063.03043
author: Eli Ben-Sasson
author: Russell Impagliazzo
author: A. Wigderson
published in: Combinatorica
publication date: 2005-07-05T00:00:00Z
Mathematics Subject Classification ID: 03F20
Mathematics Subject Classification ID: 03B35
Mathematics Subject Classification ID: 68Q17
zbMATH DE Number: 2186409
zbMATH Keywords: near optimal seperation
zbMATH Keywords: automated theorem proving
zbMATH Keywords: tree-like resolution refutations
zbMATH Keywords: general resolution refutations
zbMATH Keywords: polynomial run-time
MaRDI profile type: Publication
full work available at URL: s00493-004-0036-5
OpenAlex ID: W2092984557
DOI: 10.1007/S00493-004-0036-5
Recommended article: A characterization of tree-like resolution size
Recommended article: A Near-Optimal Separation of Regular and General Resolution
Recommended article: A lower bound for tree resolution
Recommended article: Separation algorithm for tree partitioning inequalities
Recommended article: A complexity gap for tree resolution
Recommended article: Optimal partition trees
Recommended article: Tree approximation and optimal encoding
Recommended article: Optimal multiway generalized split trees
Recommended article: Treewidth reduction for constrained separation and bipartization problems
description: scientific article; zbMATH DE number 2186409