Proof complexity

被引：5

作者：

Krajícek, J ^{[1
]}

机构：

[1] Acad Sci Czech Republic, Inst Math, CZ-11567 Prague, Czech Republic

来源：

EUROPEAN CONGRESS OF MATHEMATICS | 2005年

关键词：

WEAK PIGEONHOLE PRINCIPLE; LOWER BOUNDS; SYSTEMS;

D O I：

10.4171/009-1/14

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

This note, based on my 4ECM lecture, exposes few basic points of proof complexity in a way accessible to any mathematician.

引用

页码：221 / 231

页数：11

共 19 条

[1] Alekhnovich M, 2000, ANN IEEE SYMP FOUND, P43, DOI 10.1109/SFCS.2000.892064
[2] [Anonymous], IEEETRANSACTIONSONED, DOI DOI 10.1109/13.965782
[3] Buss Samuel R., 1986, Bounded Arithmetic
[4] Cook S. A., 1971, P 3 ANN ACM S THEOR
[5] RELATIVE EFFICIENCY OF PROPOSITIONAL PROOF SYSTEMS
COOK, SA
RECKHOW, RA
[J]. JOURNAL OF SYMBOLIC LOGIC, 1979, 44 (01) : 36 - 50
[6] Cook Stephen A., 1975, P 7 ANN ACM S THEORY, P83
[7] Hajos G., 1961, Wiss. Z.-MartinLuther-Univ. Halle-W., V10, P116
[8] Diagonalization in proof complexity
Krajícek, J
[J]. FUNDAMENTA MATHEMATICAE, 2004, 182 (02) : 181 - 192
[9] Dual weak pigeonhole principle, pseudo-surjective functions, and provability of circuit lower bounds
Krajicek, J
[J]. JOURNAL OF SYMBOLIC LOGIC, 2004, 69 (01) : 265 - 286
[10] On the weak pigeonhole principle
Krajícek, J
[J]. FUNDAMENTA MATHEMATICAE, 2001, 170 (1-2) : 123 - 140