rs_pres_holds
The lemma establishes existence of an RS-preserving reduction from constraint instances to vertex cover instances. Researchers studying reductions in the Recognition Science complexity module would cite it to confirm the mapping preserves the required structure. The proof is a direct term instantiation of the bundled reduction definition.
claimThe type of RS-preserving reductions from the constraint satisfaction problem (size measured by vertex count plus constraint count) to the vertex cover problem (size measured by vertex count plus edge count) is non-empty.
background
The module concerns mapping recognition science constraint instances, structures with vertices and constraints, to vertex cover instances consisting of vertices and edges. An upstream definition constructs an RS-preserving wrapper that specifies size measures for both sides and the explicit reduction function. The target proposition asserts the non-emptiness of the type of all such preserving reductions.
proof idea
The proof is a one-line term that supplies the upstream RS-preserving reduction definition as the inhabitant of the non-empty type.
why it matters in Recognition Science
This result confirms the existence of a structure-preserving reduction in the complexity analysis of the Recognition Science framework. It supports arguments about how recognition properties transfer across problem reductions. The declaration fills the existence claim for the reduction from constraint satisfaction to vertex cover within the RSVC module.
scope and limits
- Does not prove the reduction runs in polynomial time.
- Does not show exact preservation of solution sizes.
- Does not apply to graphs outside the defined instance structures.
- Does not address NP-completeness or approximation ratios.
formal statement (Lean)
61lemma rs_pres_holds : rs_pres_prop :=
proof body
Term-mode proof.
62 ⟨Complexity.RSVC.rs_preserving_RS2VC⟩
63
64end IndisputableMonolith
65
66end IndisputableMonolith