IndisputableMonolith.Complexity.VertexCover
This module introduces definitions for complexity pairs as functions of input size together with the vertex cover problem structure. It supplies Instance, InCover, EdgeCovered, Covers and HasCover predicates for use in dual-complexity arguments. Researchers examining ledger-style P versus NP scaffolds cite these objects. The module contains only definitions and no proofs.
claimA complexity pair consists of two functions $f,g : nmapsto cost$ of input size $n$. An instance $I$ is a graph whose edges must be covered; $InCover(v,C)$ holds when vertex $v$ belongs to cover set $C$, $EdgeCovered(e,C)$ when edge $e$ is incident to $C$, $Covers(C,I)$ when every edge is covered, and $HasCover(I,k)$ when a cover of size $k$ exists.
background
The module resides in the Complexity domain and opens with the statement that a complexity pair comprises functions of input size. It defines Instance as the data structure for a vertex-cover problem, then supplies the predicates InCover, EdgeCovered, Covers and HasCover that express membership and coverage relations on that instance. These notions sit alongside sibling definitions such as trivialInstance and trivial_hasCover, which supply the base case of an empty edge list. The surrounding Recognition Science setting treats such pairs as the cost functions that appear in ledger-style dual complexity comparisons.
proof idea
This is a definition module, no proofs.
why it matters in Recognition Science
The module supplies the vertex-cover vocabulary required by ComputationBridge, the scaffold that explores a hypothetical P versus NP resolution via ledger-style dual complexity (explicitly marked outside the verified certificate chain). It is also imported by RSVC to map Recognition Science constraint instances onto edges that must be covered. Core.Complexity likewise depends on these definitions to carry complexity measures forward.
scope and limits
- Does not establish any complexity bounds or NP-completeness statements.
- Does not participate in the verified certificate chain containing UltimateClosure.
- Does not supply concrete complexity functions beyond the abstract pair.
- Does not contain algorithms or decision procedures for the cover problem.