IndisputableMonolith.Complexity.VertexCover
This module defines complexity pairs as functions of input size together with vertex cover instances, covering relations, and basic properties. Researchers modeling dual complexity in Recognition Science cite it when mapping constraints to graph problems. The module consists entirely of definitions and supporting lemmas with no theorems or proofs.
claimA complexity pair is a pair of functions $(f,g)$ with $f,g : ℕ → ℝ_{≥0}$ of input size. An instance is a graph whose edges must be covered by a vertex subset satisfying the InCover and EdgeCovered relations.
background
The module introduces ComplexityPair as pairs of functions of input size. It defines Instance for vertex-cover graphs, InCover for membership in a cover, EdgeCovered for covered edges, Covers for the covering predicate, and HasCover for existence of a cover. These sit inside the Complexity domain and are imported by downstream modules exploring computation versus recognition.
proof idea
this is a definition module, no proofs
why it matters in Recognition Science
The module supplies vertex-cover definitions used by IndisputableMonolith.Complexity.RSVC to map RS constraints onto edges and by IndisputableMonolith.Complexity.ComputationBridge for its hypothetical P-vs-NP scaffold. It also supports IndisputableMonolith.Core.Complexity. It provides the complexity-pair foundation referenced in the ComputationBridge scaffold note.
scope and limits
- Does not contain any verified theorems or closure results.
- Does not participate in the main certificate chain.
- Does not assert a P-vs-NP resolution.
- Does not supply numerical bounds or runtime estimates.