Space complexity in propositional calculus

被引:89
作者
Alekhnovich, M [1 ]
Ben-Sasson, E
Razborov, AA
Wigderson, A
机构
[1] Moscow MV Lomonosov State Univ, Moscow, Russia
[2] Hebrew Univ Jerusalem, Inst Comp Sci, Jerusalem, Israel
[3] VA Steklov Math Inst, Moscow 117333, Russia
关键词
proof complexity; resolution; Frege; polynomial calculus;
D O I
10.1137/S0097539700366735
中图分类号
TP301 [理论、方法];
学科分类号
081202 ;
摘要
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 to 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.
引用
收藏
页码:1184 / 1211
页数:28
相关论文
共 17 条
[1]   MINIMAL NON-2-COLORABLE HYPERGRAPHS AND MINIMAL UNSATISFIABLE FORMULAS [J].
AHARONI, R ;
LINIAL, N .
JOURNAL OF COMBINATORIAL THEORY SERIES A, 1986, 43 (02) :196-204
[2]  
BEAME P, 1998, B EATCS, V65, P66
[3]  
BONET ML, 1999, P 40 ANN S FDN COMP, P422
[4]  
Clegg M., 1996, Proceedings of the Twenty-Eighth Annual ACM Symposium on the Theory of Computing, P174, DOI 10.1145/237814.237860
[5]   RELATIVE EFFICIENCY OF PROPOSITIONAL PROOF SYSTEMS [J].
COOK, SA ;
RECKHOW, RA .
JOURNAL OF SYMBOLIC LOGIC, 1979, 44 (01) :36-50
[6]  
ESTEBAN JL, 1999, P 16 STACS, P530
[7]   Lower bounds for the polynomial calculus and the Grobner basis algorithm [J].
Impagliazzo, R ;
Pudlák, P ;
Sgall, J .
COMPUTATIONAL COMPLEXITY, 1999, 8 (02) :127-144
[8]  
KOZEN D., 1977, P 18 ANN S FDN COMP, P254
[9]  
Krajicek Jan, 1995, BOUNDED ARITHMETIC P
[10]  
KRISHNAMURTHY B, 1985, ACTA INFORM, V22, P253, DOI 10.1007/BF00265682