文章基本信息
- 标题：Total space in Resolution is at least width squared
- 本地全文：下载
- 作者：Ilario Bonacina
- 期刊名称：Electronic Colloquium on Computational Complexity
- 印刷版ISSN：1433-8092
- 出版年度：2016
- 卷号：2016
- 出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
- 摘要：
Given an unsatisfiable k -CNF formula 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 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 , where the size of the memory is measured as the total number of literals it can contain. We prove that T = (( W − k ) 2 ) .
- 关键词：Resolution ; Total Space ; width
