Exponential separation between Res(\(k\)) and Res(\(k+1\)) for \(k \leqslant \varepsilon\log n\)
type: Item
instance of: scholarly article
title: Exponential separation between Res(\(k\)) and Res(\(k+1\)) for \(k \leqslant \varepsilon\log n\)
zbMATH Open document ID: 1173.68714
author: Nathan Segerlind
published in: Information Processing Letters
publication date: 2009-08-27T00:00:00Z
Mathematics Subject Classification ID: 68T15
zbMATH DE Number: 5599205
zbMATH Keywords: propositional proof complexity
zbMATH Keywords: lower bounds
zbMATH Keywords: \(k\)-DNFs
zbMATH Keywords: resolution
zbMATH Keywords: Res(\(k\))
zbMATH Keywords: switching lemmas
zbMATH Keywords: random restrictions
zbMATH Keywords: theory of computation
zbMATH Keywords: computational complexity
MaRDI profile type: Publication
full work available at URL: j.ipl.2004.09.024
OpenAlex ID: W1494548287
cites work: On the automatizability of resolution and related propositional proof systems
cites work: A Switching Lemma for Small Restrictions and Lower Bounds for k-DNF Resolution
cites work: Unrestricted resolution versus N-resolution
DOI: 10.1016/J.IPL.2004.09.024
description: scientific article; zbMATH DE number 5599205