POLYNOMIAL SIZE PROOFS OF THE PROPOSITIONAL PIGEONHOLE PRINCIPLE

被引：107

作者：

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 [J].

COOK, SA ;

RECKHOW, RA .

[3]

FURST M, 1981, IEEE S F COMPUTING, V22, P260

[4] THE INTRACTABILITY OF RESOLUTION [J].

HAKEN, A .

[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 [J].

URQUHART, A .

[10]

WILKIE A, 1984, LOGIC C 84 MANCHESTE