POLYNOMIAL SIZE PROOFS OF THE PROPOSITIONAL PIGEONHOLE PRINCIPLE

被引：106

作者：

BUSS, SR ^{[1
]}

机构：

[1] MATH SCI RES INST,BERKELEY,CA 94720

来源：

关键词：

D O I：

10.2307/2273826

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

引用

页码：916 / 927

页数：12

共 12 条

[1] Buss S. R., 1985, THESIS PRINCETON U P
[2] RELATIVE EFFICIENCY OF PROPOSITIONAL PROOF SYSTEMS
COOK, SA
RECKHOW, RA
[J]. JOURNAL OF SYMBOLIC LOGIC, 1979, 44 (01) : 36 - 50
[3] FURST M, 1981, IEEE S F COMPUTING, V22, P260
[4] THE INTRACTABILITY OF RESOLUTION
HAKEN, A
[J]. THEORETICAL COMPUTER SCIENCE, 1985, 39 (2-3) : 297 - 308
[5] PARIS J, 1985, LECT NOTES MATH, V1130, P317
[6] SAVAGE JE, 1976, COMPLEXITY COMPUTING
[7] Statman R., 1977, LOGIC C 76, P505
[8] Tseitin G., 1970, SEMINARS MATH, V8, P115
[9] HARD EXAMPLES FOR RESOLUTION
URQUHART, A
[J]. JOURNAL OF THE ACM, 1987, 34 (01) : 209 - 219
[10] WILKIE A, 1984, LOGIC C 84 MANCHESTE