Worked examples

Tutorial-style, domain-specific worked examples: each file walks through the addition of a new problem domain to the library, in the order a user meets it – the concrete problem in their own formalism, its machine-checked encoding (size bounds discharged at construction), the abstract vocabulary and semantics, the faithfulness theorem tying the two, and then NP membership, hardness and completeness of the encoded variant – and is meant to be read top to bottom as a template for new formalizations.

• DescriptiveComplexity.Examples.ConjunctiveQueries: Boolean conjunctive queries over relational databases – evaluation and containment, both NP-complete (Chandra & Merlin 1977), with the Chandra–Merlin homomorphism theorem as the bridge between them. Order-free, quantifier-free reductions; the file opens with the concrete list-of-atoms instances and their encoding.
• DescriptiveComplexity.Examples.GraphCrawling: Web data acquisition as graph crawling – NP-complete (Gauquier–Manolescu–Senellart 2026), by the paper's reduction from Set Cover. Read second: it exercises what the CQ tutorial does not – a cardinality threshold, a reachability certificate, an ordered FO reduction, and a single-sorted concrete encoding. It closes with the restriction to depth-2 websites and with a quota variant (a crawl of at most B pages containing at least K targets), NP-complete by an order-free reduction from the base problem.
• DescriptiveComplexity.Examples.ProbabilisticQueries: query evaluation over probabilistic databases, the first tutorial about a counting problem. The count of the possible worlds of the query R(x), S(x, y), T(y) is one-call #P-complete (Dalvi and Suciu 2012), by a parsimonious reduction from #PP2DNF; membership in #P holds for every first-order query. With probabilities in the instance, written in binary, the probability of any first-order query is a ratio of two #P numbers; a concrete database type, computed, faithfully encoded and decoded, follows. The file closes on the other side of the dichotomy of Dalvi and Suciu: on the same instances, the weighted count of the query R(x), S(x, y) is in FP, failing being a product over independent facts and a first-success identity turning the complement into a quantitative term with no subtraction.