文章基本信息

标题：Total Space in Resolution Is at Least Width Squared
本地全文：下载
作者：Ilario Bonacina
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2016
卷号：55
页码：56:1-56:13
DOI：10.4230/LIPIcs.ICALP.2016.56
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：Given an unsatisfiable k-CNF formula phi we consider two complexity measures in Resolution: width and total space. The width is the minimal W such that there exists a Resolution refutation of phi with clauses of at most W literals. The total space is the minimal size T of a memory used to write down a Resolution refutation of phi where the size of the memory is measured as the total number of literals it can contain. We prove that T = Omega((W - k)^2).
关键词：Resolution; width; total space