Concepedia

Proof Complexity Of Propositional Logic

Proof Complexity of Propositional Logic is a branch of computational complexity theory that studies the intrinsic difficulty of proving propositional tautologies by analyzing the minimal lengths of proofs in various propositional proof systems.

45

Publications

2.6K

Citations

53

Authors

37

Institutions

Publications per year

2017–2026

3

Parents

Publications

45

Hard examples for resolution

Alasdair Urquhart · Journal of the ACM · 1987 · 451 citations · Full text

, , +16

The Complexity of Propositional Proofs

Alasdair Urquhart · Bulletin of Symbolic Logic · 1995 · 225 citations

, , +16

Propositional proof systems, the consistency of first order theories and the complexity of computations

Jan Krajı́ček, Pavel Pudlák · Journal of Symbolic Logic · 1989 · 202 citations

, , +11

The Complexity of Propositional Proofs

Nathan Segerlind · Bulletin of Symbolic Logic · 2007 · 182 citations

, , +16

Lower bounds to the size of constant-depth propositional proofs

Jan Krajı́ček · Journal of Symbolic Logic · 1994 · 160 citations

, , +13

1–5 of 45

Authors

53

  1. SC
    Stephen Cook

    University of Toronto, Canada

    5 publications · 205 citations

    5

    h-index

  2. AU
    Alasdair Urquhart

    University of Toronto, Canada

    5 publications · 904 citations

    5

    h-index

  3. JK
    Jan Krajı́ček

    Czech Academy of Sciences, Institute of Mathematics, Czechia

    5 publications · 469 citations

    5

    h-index

  4. SR
    Samuel R. Buss

    University of California San Diego, United States

    4 publications · 125 citations

    4

    h-index

  5. TP
    Toniann Pitassi

    University of Toronto, Canada

    3 publications · 242 citations

    3

    h-index

1–5 of 53

Institutions

37

  1. University of California San Diego

    San Diego, United States

    6 h-index

    7 publications

    323 citations

  2. University of Toronto

    Toronto, Canada

    6 h-index

    8 publications

    1.1K citations

  3. Czech Academy of Sciences, Institute of Mathematics

    Prague, Czechia

    3 h-index

    3 publications

    216 citations

  4. McMaster University

    Hamilton, Canada

    2 h-index

    2 publications

    69 citations

  5. Charles University

    Prague, Czechia

    2 h-index

    2 publications

    76 citations

  6. University of Białystok

    Bialystok, Poland

    2 h-index

    2 publications

    59 citations

  7. TU Wien

    Vienna, Austria

    2 h-index

    2 publications

    44 citations

  8. Lomonosov Moscow State University

    Moscow, Russia

    2 h-index

    2 publications

    86 citations

1–8 of 37

Venues

  1. Annals of Pure and Applied Logic

    5 publications · 138 citations

    5

    h-index

  2. SIAM Journal on Computing

    3 publications · 211 citations

    3

    h-index

  3. Journal of Symbolic Logic

    3 publications · 412 citations

    3

    h-index

  4. Bulletin of Symbolic Logic

    2 publications · 407 citations

    2

    h-index

  5. Journal of the ACM

    JACM · 2 publications · 473 citations

    2

    h-index

1–5