IndisputableMonolith.Complexity.RSVC
The RSVC module maps Recognition Science constraint instances to vertex cover graphs. It defines ConstraintInstance, the toVC mapping, and reduction functions like reduceRS2VC together with correctness lemmas. Researchers examining dual computation-recognition complexity models cite it to translate RS problems into covering instances. The module consists of type definitions, predicates such as Recognizes, and supporting reduction lemmas.
claimAn RS constraint instance $C$ maps to a vertex cover instance $(G,k)$ via toVC, where the edges of $G$ encode the constraints of $C$ that must be covered; the reduction satisfies rs_preserving and reduce_correct.
background
The module imports VertexCover, which defines complexity as pairs of functions of input size. It introduces ConstraintInstance as the representation of an RS problem and the predicate Recognizes to express when a solution covers the instance. The setting is the reduction of RS problems to the vertex cover decision problem, with auxiliary definitions IsPolynomial and RSPreserving to track preservation properties.
proof idea
This is a definition module. It declares ConstraintInstance and toVC, then states the reduction reduceRS2VC and proves its correctness in reduce_correct by direct verification that the mapped graph edges correspond to the original constraints.
why it matters in Recognition Science
The module supplies the RS-to-VC reduction used by the ComputationBridge scaffold, which explores hypothetical P versus NP resolutions via ledger-style dual complexity. It also feeds Core.Complexity to integrate the reduction into the broader framework. The mapping fills the step that converts RS constraint instances into graph covering problems for complexity classification.
scope and limits
- Does not resolve P versus NP.
- Does not supply polynomial algorithms for the reduced instances.
- Does not verify the mapping on concrete numerical RS examples.
- Does not extend beyond the defined reduction to other NP-complete problems.