期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：1999
卷号：1999
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：We study space complexity in the framework of
propositional proofs. We consider a natural model analogous to
Turing machines with a read-only input tape, and such
popular propositional proof systems as Resolution, Polynomial
Calculus and Frege systems. We propose two different space measures,
corresponding to the maximal number of bits, and clauses/monomials that
need be kept in the memory simultaneously. We prove a number of lower
and upper bounds in these models, as well as some structural
results concerning the clause space for Resolution and Frege Systems.
关键词：frege, Polynomial Calculus, propositional proof complexity, Resolution, space complexity
