Propositional proof complexity (Q6064569)

From MaRDI portal
scientific article; zbMATH DE number 7763400
Language Label Description Also known as
English
Propositional proof complexity
scientific article; zbMATH DE number 7763400

    Statements

    Propositional proof complexity (English)
    0 references
    10 November 2023
    0 references
    Summary: Propositional proof complexity studies efficient provability of those statements that can be expressed in propositional logic, in various proof systems, and under various notions of ``efficiency.'' Proof systems and statements of interest come from a variety of sources that, besides logic and combinatorics, include many other areas like combinatorial optimization and practical SAT solving. This article is an expanded version of the ECM talk in which we will attempt to convey some basic ideas underlying this vibrant area. For the entire collection see [Zbl 1519.00033].
    0 references
    proof complexity
    0 references
    lower bounds
    0 references
    resolution
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references

    Identifiers

    0 references
    0 references
    0 references