Concepedia

Proof Complexity Of Quantified Boolean Formulas

The Proof Complexity of Quantified Boolean Formulas is a subfield of computational complexity theory that studies the inherent resource requirements of proof systems for verifying the validity or invalidity of quantified Boolean formulas, distinguished by its focus on the interplay between quantifier alternation and the succinctness or efficiency of propositional reasoning.

6

Publications

981

Citations

8

Authors

8

Institutions

Publications per year

2017–2026

3

Variants

Qbf Proof Complexity

Parents

Publications

6

Handbook of mathematical logic, edited by Jon Barwise with the cooperation of H. J. Keisler, K. Kunen, Y. N. Moschovakis, and A. S. Troelstra, Studies in logic and the foundations of mathematics, vol. 90, North-Holland Publishing Company, Amsterdam, New York, and Oxford, 1978 (© 1977), xi + 1165 pp. - C. Smoryński. D.1. The incompleteness theorems. Pp. 821–865. - Helmut Schwichtenberg. D.2. Proof theory: some applications of cut-elimination. Pp. 867–895. - Richard Statman. D.3. Herbrand's theorem and Gentzen's notion of a direct proof. Pp. 897–912. - Solomon Feferman. D.4. Theories of finite type related to mathematical practice. Pp. 913–971. - A. S. Troelstra. D.5. Aspects of constructive mathematics. Pp. 973–1052. - Michael P. Fourman. D.6. The logic of topoi. Pp. 1053–1090. - Henk P. Barendregt. D.1. The type free lambda calculus. Pp. 1091–1132. - Jeff Paris and Leo Harrington. D.8. A mathematical incompleteness in Peano arithmetic. Pp. 1133–1142.

William A. Howard · Journal of Symbolic Logic · 1984 · 840 citations

, , +11

Proof Complexity of Resolution-based QBF Calculi

Olaf Beyersdorff, Leroy Chew, Mikoláš Janota · DROPS (Schloss Dagstuhl – Leibniz Center for Informatics) · 2015 · 51 citations · Full text

, , +15

New Resolution-Based QBF Calculi and Their Proof Complexity

Olaf Beyersdorff, Leroy Chew, Mikoláš Janota · ACM Transactions on Computation Theory · 2019 · 34 citations

, , +13

A note on SAT algorithms and proof complexity

Jan Krajı́ček · Information Processing Letters · 2012 · 33 citations

, , +12

Are Short Proofs Narrow? QBF Resolution Is <i>Not</i> So Simple

Olaf Beyersdorff, Leroy Chew, Meena Mahajan et al. · ACM Transactions on Computational Logic · 2017 · 13 citations · Full text

, , +16

1–5 of 6

Authors

8

  1. LC
    Leroy Chew

    University of Leeds, United Kingdom

    3 publications · 98 citations

    3

    h-index

  2. OB
    Olaf Beyersdorff

    University of Leeds, United Kingdom

    3 publications · 98 citations

    3

    h-index

  3. MJ
    Mikoláš Janota

    Instituto de Engenharia de Sistemas e Computadores Investigação e Desenvolvimento, Portugal

    2 publications · 85 citations

    2

    h-index

  4. WA
    William A. Howard

    Columbia University, United States

    1 publications · 840 citations

    1

    h-index

  5. HC
    Hubie Chen

    Ikerbasque, Spain

    1 publications · 10 citations

    1

    h-index

1–5 of 8

Institutions

8

  1. University of Leeds

    Leeds, United Kingdom

    3 h-index

    5 publications

    162 citations

  2. Instituto de Engenharia de Sistemas e Computadores Investigação e Desenvolvimento

    Lisbon, Portugal

    2 h-index

    2 publications

    85 citations

  3. Institute for Systems Engineering and Computers

    Lisbon, Portugal

    1 h-index

    1 publications

    51 citations

  4. University of Lisbon

    Lisbon, Portugal

    1 h-index

    1 publications

    34 citations

  5. Charles University

    Prague, Czechia

    1 h-index

    1 publications

    33 citations

  6. Friedrich Schiller University Jena

    Jena, Germany

    1 h-index

    1 publications

    34 citations

  7. Institute of Mathematical Sciences

    Chennai, India

    1 h-index

    2 publications

    26 citations

  8. Ikerbasque

    Bilbao, Spain

    1 h-index

    1 publications

    10 citations

1–8 of 8

Venues

  1. ACM Transactions on Computation Theory

    TOCT · 2 publications · 44 citations

    2

    h-index

  2. DROPS (Schloss Dagstuhl – Leibniz Center for Informatics)

    Repository · 1 publications · 51 citations

    1

    h-index

  3. ACM Transactions on Computational Logic

    TOCL · 1 publications · 13 citations

    1

    h-index

  4. Information Processing Letters

    1 publications · 33 citations

    1

    h-index

  5. Journal of Symbolic Logic

    1 publications · 840 citations

    1

    h-index

1–5