IndisputableMonolith.Complexity.VertexCover
The VertexCover module defines complexity pairs as pairs of functions of input size together with vertex cover instances, membership predicates, and cover relations. Researchers exploring dual computation-recognition complexity for P versus NP questions would cite these definitions. The module consists entirely of type and predicate definitions with only trivial supporting lemmas.
claimA complexity pair is a pair of functions $(f,g)$ with $f,g : nats → reals$ giving costs as functions of input size. An instance is a graph; $InCover$, $EdgeCovered$, $Covers$, and $HasCover$ are the standard membership and existence predicates for a vertex cover.
background
The module sits in the Complexity domain and imports only Mathlib. Its central object is the ComplexityPair type, described as functions of input size. Sibling definitions introduce Instance, InCover, EdgeCovered, Covers, HasCover, and trivial constructors such as trivialInstance and trivial_hasCover. These supply the concrete predicates needed to encode vertex cover as a recognition problem.
proof idea
This is a definition module, no proofs.
why it matters in Recognition Science
The definitions feed the RSVC module (RS constraint instance mapped to edges to be covered), the ComputationBridge scaffold (hypothetical P versus NP framework based on ledger-style dual complexity), and Core.Complexity. The module therefore supplies the vertex-cover encoding required for any downstream exploration of recognition versus computation cost.
scope and limits
- Does not prove any relation between P and NP.
- Does not derive complexity bounds or reductions.
- Does not reference the forcing chain, phi-ladder, or Recognition Composition Law.
- Does not contain verified certificates or closure theorems.