Propositional proof complexity (Q6064569)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 7763400
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| 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.8353184461593628
0 references
0.8143966197967529
0 references
