Concepedia

Extended Frege

Extended Frege is a propositional proof system in proof complexity that extends the classical Frege system by allowing the introduction of new propositional variables and abbreviations for arbitrary formulas, thereby enabling polynomial-size representations of proofs that would require exponential size in the standard Frege system.

15

Publications

1.4K

Citations

20

Authors

17

Institutions

Publications per year

2017–2026

2

Variants

EfExtended Frege System

Parents

Publications

15

The relative efficiency of propositional proof systems

Stephen Cook, Robert A. Reckhow · Journal of Symbolic Logic · 1979 · 827 citations

, , +15

Frege and other philosophers

Choice Reviews Online · 1991 · 163 citations

, , +9

Minimum propositional proof length is NP-hard to linearly approximate

Michael Alekhnovich, Sam Buss, Shlomo Moran et al. · Journal of Symbolic Logic · 2001 · 50 citations

, , +15

The Complexity of the Hajós Calculus

Toniann Pitassi, Alasdair Urquhart · SIAM Journal on Discrete Mathematics · 1995 · 45 citations

, , +14

ON THE PROOF COMPLEXITY OF THE NISAN–WIGDERSON GENERATOR BASED ON A HARD <font>NP</font> ∩ <font>coNP</font> FUNCTION

Jan Krajı́ček · Journal of Mathematical Logic · 2011 · 42 citations

, , +13

1–5 of 15

Authors

20

  1. TP
    Toniann Pitassi

    University of Toronto, Canada

    3 publications · 111 citations

    3

    h-index

  2. JP
    Ján Pich

    University of Oxford, United Kingdom

    2 publications · 56 citations

    2

    h-index

  3. SB
    Sam Buss

    University of California San Diego, United States

    2 publications · 84 citations

    2

    h-index

  4. EJ
    Emil Jeřábek

    Czech Academy of Sciences, Institute of Mathematics, Czechia

    2 publications · 33 citations

    2

    h-index

  5. OB
    Olaf Beyersdorff

    University of Leeds, United Kingdom

    2 publications · 56 citations

    2

    h-index

1–5 of 20

Institutions

17

  1. University of Toronto

    Toronto, Canada

    4 h-index

    4 publications

    885 citations

  2. Charles University

    Prague, Czechia

    2 h-index

    2 publications

    70 citations

  3. University of California San Diego

    San Diego, United States

    2 h-index

    2 publications

    84 citations

  4. University of Leeds

    Leeds, United Kingdom

    2 h-index

    3 publications

    98 citations

  5. Universitat Politècnica de Catalunya

    Barcelona, Spain

    1 h-index

    1 publications

    14 citations

  6. Swansea University

    Swansea, United Kingdom

    1 h-index

    1 publications

    34 citations

  7. Universitat de Barcelona

    Barcelona, Spain

    1 h-index

    1 publications

    28 citations

  8. Moscow State University

    Dushanbe, Tajikistan

    1 h-index

    1 publications

    50 citations

1–8 of 17

Venues

  1. Journal of Symbolic Logic

    3 publications · 904 citations

    3

    h-index

  2. Annals of Pure and Applied Logic

    2 publications · 33 citations

    2

    h-index

  3. SIAM Journal on Discrete Mathematics

    1 publications · 45 citations

    1

    h-index

  4. Journal of Philosophical Logic

    1 publications · 28 citations

    1

    h-index

  5. ACM Transactions on Computational Logic

    TOCL · 1 publications · 34 citations

    1

    h-index

1–5