Concepedia

Proof Search Complexity

Proof Search Complexity is a theoretical framework in computational logic that measures the computational resources required to find proofs within propositional proof systems, distinguished from related complexity notions by focusing on the search process rather than the size or structure of proofs themselves.

41

Publications

2.2K

Citations

69

Authors

47

Institutions

Publications per year

2017–2026

3

Parents

Publications

41

Logic Programming with Focusing Proofs in Linear Logic

Jean‐Marc Andreoli · Journal of Logic and Computation · 1992 · 652 citations

, , +13

On the complexity of cutting-plane proofs

William J. Cook, Collette R. Coullard, Gy. Turán · Discrete Applied Mathematics · 1987 · 271 citations

, , +9

Upper and lower bounds for tree-like cutting planes proofs

Russell Impagliazzo, Toniann Pitassi, Alasdair Urquhart · 2002 · 123 citations

, , +15

Bounds for proof-search and speed-up in the predicate calculus

Richard Statman · Annals of Mathematical Logic · 1978 · 107 citations · Full text

, , +11

The number of proof lines and the size of proofs in first order logic

Jan Krajı́ček, Pavel Pudlák · Archive for Mathematical Logic · 1988 · 90 citations

, , +14

1–5 of 41

Authors

69

  1. UE
    Uwe Egly

    TU Wien, Austria

    2 publications · 32 citations

    2

    h-index

  2. AK
    Akihiro Kishimoto

    University of Alberta, Canada

    2 publications · 48 citations

    2

    h-index

  3. MM
    Martin Müller

    University of Alberta, Canada

    2 publications · 48 citations

    2

    h-index

  4. RK
    Roman Kuznets

    University of Bern, Switzerland

    2 publications · 52 citations

    2

    h-index

  5. JK
    Jan Krajı́ček

    Czech Academy of Sciences, Institute of Mathematics, Czechia

    2 publications · 124 citations

    2

    h-index

1–5 of 69

Institutions

47

  1. TU Wien

    Vienna, Austria

    5 h-index

    8 publications

    179 citations

  2. University of Alberta

    Edmonton, Canada

    2 h-index

    3 publications

    62 citations

  3. University of California San Diego

    San Diego, United States

    2 h-index

    2 publications

    141 citations

  4. Carnegie Mellon University

    Pittsburgh, United States

    2 h-index

    2 publications

    128 citations

  5. Cornell University

    Ithaca, United States

    2 h-index

    2 publications

    286 citations

  6. Maastricht University

    Maastricht, The Netherlands

    2 h-index

    8 publications

    129 citations

  7. Google (United States)

    Mountain View, United States

    1 h-index

    1 publications

    11 citations

  8. Universitat Politècnica de Catalunya

    Barcelona, Spain

    1 h-index

    2 publications

    118 citations

1–8 of 47

Venues

  1. Theoretical Computer Science

    3 publications · 99 citations

    3

    h-index

  2. Information Sciences

    2 publications · 35 citations

    2

    h-index

  3. International Joint Conference on Artificial Intelligence

    Conference · 2 publications · 45 citations

    2

    h-index

  4. Electronic Notes in Theoretical Computer Science

    ENTCS · 2 publications · 33 citations

    2

    h-index

  5. Logic Journal of IGPL

    2 publications · 33 citations

    2

    h-index

1–5