Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR09-047 | 20th April 2009 00:00

A Space Hierarchy for k-DNF Resolution


Authors: Eli Ben-Sasson, Jakob Nordström
Publication: 31st May 2009 13:35
Downloads: 1937


The k-DNF resolution proof systems are a family of systems indexed by
the integer k, where the kth member is restricted to operating with
formulas in disjunctive normal form with all terms of bounded arity k
(k-DNF formulas). This family was introduced in [Krajicek 2001] as an
extension of the well-studied resolution proof system. A number of
lower bounds have been proven on k-DNF resolution proof length and
space, and it has also been shown that (k+1)-DNF resolution is
exponentially more powerful than k-DNF resolution for all k with
respect to length. For proof space, however, no corresponding
hierarchy has been known except for the (very weak) subsystems
restricted to tree-like proofs. In this work, we establish a strict
space hierarchy for the general, unrestricted k-DNF resolution proof


Comment #1 to TR09-047 | 11th August 2010 18:58

This report has been subsumed

Comment #1
Authors: Eli Ben-Sasson, Jakob Nordström
Accepted on: 11th August 2010 18:58
Downloads: 1158


We have merged and updated our two ECCC technical reports TR09-034 and TR09-047, and published them as a new ECCC report TR10-125. (An identical version of the new report has also been posted to ArXiv.)

This new paper subsumes the previous two papers.

ISSN 1433-8092 | Imprint