期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：2009
卷号：2009
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：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 systems.
关键词：k-DNF resolution , Proof Complexity , separation , size , Space , Space Hierarchy , trade-off
