Repository navigation
v1.4.0 – for Mathlib v4.35.0
Requires Mathlib v4.35.0 and toolchain leanprover/lean4:v4.35.0.
This release adds counting complexity (#P, FP, and the decision classes
defined by counting), registers the library in the Lax archive, moves to
Mathlib v4.35.0, and adopts Lean's module system, so the library now has a
public interface and a private implementation.
Changes since v1.3.0
- Counting classes. The library now covers function problems: a problem
whose answer is a number. #P is the class of functions counting the
witnesses of an ∃SO sentence, and equals ΣQSO(FO). FP, the
polynomial-time functions, is defined by quantitative first-order logic over
least fixed points; the number written by a circuit, by a machine, and by
unit propagation are FP-complete. There are four kinds of counting
reductions: parsimonious, relativized parsimonious, one-call (metric
reductions in the literature), and subtractive. #P is closed under all four,
andHardandCompletefor #P refer to one-call and subtractive
reductions. - The #P catalog. Seventeen problems are parsimoniously #P-complete. Each
counts the solutions of an NP-catalog problem at exactly the threshold
size: #SAT, #3SAT, #1-in-SAT, #Clique, #Independent Set, #Vertex Cover, #Set
Packing, #Set Cover, #Hitting Set, #Dominating Set, #Feedback Vertex
Set, #Feedback Arc Set, #Steiner Tree, #Exact Cover, #Knapsack, #0-1 Integer
Programming, and #Hamilton Circuit, directed and undirected. Eleven more are
complete under one-call or subtractive reductions, among
them #DNF, #2SAT, #HORN-SAT, #BIS, #PP2DNF, and the permanent as #Cycle Cover
(Valiant's theorem). - Decision classes defined by counting. ⊕P, Mod_k P, PP, C₌P, and UP are
defined as properties of witness counts, with their inclusions among
themselves, NP, and coNP, and a complete problem for each class where one is
known. - Probabilistic query evaluation. Possible worlds, weighted worlds, and
the probability of a query as a ratio of two #P numbers. #PP2DNF and the
tutorial query h0 are one-call #P-complete, with the Provan–Ball and
Dalvi–Suciu attributions. - Lax archive. Nineteen submissions are registered in the Lax
archive, from the Cook–Levin theorem and the NP
catalog to the counting classes, probabilistic query evaluation, the
exponential classes, and wide machines. The README lists them, and the
docstring of each registered theorem names its statement in the archive. The
submissions are underlax/, excluded from release archives. - Encodings.
BinarySubsetSum.exists_selection_iffreads any selection
problem on an encoded subset-sum instance, with any condition on the
selection's emptiness and total, back to sets of list positions; a dependent
problem gets its faithfulness from this one lemma. - Mathlib
v4.35.0(Leanv4.35.0). The pins move, and the build is
warning-free under the new unused-tactic linter. - The module system. Every file is a
module. The public interface is
what the documentation shows: vocabularies, semantics, classes,
interpretations, reduction terms, the theorems named by the README, the
documentation landing page, the paper, and the Lax exports, and what their
statements mention. Everything else is private: helper lemmas, gadget
formulas, and auxiliary definitions, about eight thousand declarations.
This breaks dependents that used implementation lemmas, since a private
declaration cannot be imported from another package. If you relied on one,
open an issue and it can be made public. Proof-only imports are private to
their file too, so a dependent that received a Mathlib name through the
library may need to import its module.
Use
From Reservoir, in a lakefile.lean:
require "PierreSenellart" / "descriptive-complexity" @ "~1.4.0"or from git:
require "descriptive-complexity" from git
"https://github.com/PierreSenellart/descriptive-complexity" @ "v1.4.0"See the compatibility table
for which version to use with which Mathlib.
Full changelog: v1.3.0...v1.4.0