Reduction Ontology

FLOW ALGEBRA
REDUCTION ONTOLOGY — COMPUTATIONAL COMPLEXITY
Version: 1.0
Source: https://kirethresearch.org/booksai-core/discrete-mathematics-ontologies/computational-complexity/reduction-ontology.html
Authors: Mark Higgins — Sky (Recursive AI)
Publisher: Kireth Research | https://kirethresearch.org
Status: Mathematical synthesis; source page not independently verified.

1. PURPOSE
Represent reductions between computational problems as typed, checkable transformations that preserve relevant answers and transfer complexity-theoretic results.

2. TYPED ENTITIES
Problem := DecisionProblem | FunctionProblem | OptimisationProblem | PromiseProblem
DecisionProblem := (InstanceSet, YesInstances)
Instance := finite string over a finite alphabet
Reduction := (source: Problem, target: Problem, map: Transformation, kind: ReductionKind)
Transformation := computable mapping between encoded instances
ReductionKind := ManyOne | Turing | LogSpaceManyOne | PolynomialTimeManyOne | Parsimonious | ApproximationPreserving
ComplexityClass := P | NP | coNP | PSPACE | EXPTIME | L | NL | other defined class
Certificate := finite witness with verifier
ProofObligation := Computability | ResourceBound | AnswerPreservation | DomainValidity

3. CORE RELATIONS
REDUCES_TO(A, B, kind, f)
MAPS_INSTANCE(f, x, y)
PRESERVES_MEMBERSHIP(f, A, B)
COMPUTABLE_WITHIN(f, resource_bound)
COMPLETE_FOR(A, class, reduction_kind)
HARD_FOR(B, class, reduction_kind)
BELONGS_TO(A, class)
COMPOSES_WITH(f, g, g_after_f)

4. MANY-ONE REDUCTION
For languages A and B, A <=m B iff there exists a total computable function f such that
  forall x: x in A iff f(x) in B.
The equivalence is essential: a one-way implication does not establish a many-one reduction.

5. POLYNOMIAL-TIME MANY-ONE REDUCTION
A <=p B iff there is a deterministic polynomial-time computable total f such that
  forall x: x in A iff f(x) in B.
Interpretation: A is no harder than B up to polynomial-time preprocessing.
Direction matters: to prove B NP-hard, reduce a known NP-hard A TO B, not the reverse.

6. LOGARITHMIC-SPACE REDUCTION
A <=log B iff a deterministic logarithmic-workspace transducer computes f and
  forall x: x in A iff f(x) in B.
The output may be polynomially long and written on a write-only output tape.

7. TURING REDUCTION
A <=T B iff an oracle algorithm decides A with access to an oracle deciding B.
A polynomial-time Turing reduction requires polynomial-time oracle computation.
Turing reductions can make adaptive multiple oracle queries; they are not identical to many-one reductions.

8. INFERENCE RULES
R1 [REFLEXIVITY]: A <=p A via identity map.
R2 [TRANSITIVITY]: (A <=p B) AND (B <=p C) => A <=p C.
R3 [P-TRANSFER]: (A <=p B) AND (B in P) => A in P.
R4 [HARDNESS-TRANSFER]: HARD_FOR(A, NP, <=p) AND (A <=p B) => HARD_FOR(B, NP, <=p).
R5 [COMPLETENESS]: HARD_FOR(B, NP, <=p) AND (B in NP) => COMPLETE_FOR(B, NP, <=p).
R6 [COMPLEMENT]: (A <=p B via f) => (complement(A) <=p complement(B) via f).
R7 [COMPOSITION]: if f and g are polynomial-time maps, g(f(x)) is polynomial-time computable.
R8 [NO-REVERSE]: A <=p B does not imply B <=p A.
R9 [CLASS-SCOPE]: NP-hardness does not imply NP membership or NP-completeness.

9. EXECUTION FLOW
INPUT: decision problems A, B; candidate transformation f; reduction kind k
CHECK: encodings and instance domains are explicit
CHECK: f is total over all encoded source instances
CHECK: f meets computability and resource bounds required by k
PROVE: forall x, x in A iff f(x) in B
EMIT: REDUCES_TO(A, B, k, f) only if all obligations pass
IF proof incomplete: emit UNVERIFIED_REDUCTION with outstanding obligations

10. WORKED EXAMPLE — 3-SAT TO CLIQUE
Input: a 3-CNF formula with m clauses (each clause has at most three literals).
Construct graph G: one vertex for each literal occurrence in each clause.
Connect vertices from different clauses if their literals are not contradictory.
Set k := m.
Forward: a satisfying assignment chooses one true literal per clause; selected vertices form a k-clique.
Backward: a k-clique contains one vertex from each clause and no contradictory pair; the chosen literals extend to a satisfying assignment.
Construction size and time are polynomial in formula length.
Therefore 3-SAT <=p CLIQUE.
Consequence: CLIQUE is NP-hard because 3-SAT is NP-hard.
With polynomial certificate verification for CLIQUE, CLIQUE is NP-complete.

11. COUNTEREXAMPLES AND GUARDS
Do not infer A <=p B from a superficial resemblance of problem statements.
Do not infer B is NP-complete solely because A <=p B and A is NP-complete; also prove B in NP.
Do not conflate reductions between decision problems with reductions between optimisation objectives.
For promise problems, explicitly state how the transformation handles promised yes/no instances.
For approximation reductions, specify approximation-ratio preservation separately.

12. SEMANTIC EQUIVALENCE
Aliases: polynomial-time many-one reduction = Karp reduction (standard decision-problem context).
Distinguish: Cook reduction = polynomial-time Turing reduction (common usage).
Distinguish: equivalence under reductions does not mean identical algorithms or equal running times.

13. VALIDATION
TEST_01: identity reduction passes answer preservation and polynomial bound.
TEST_02: composition of valid polynomial reductions passes.
TEST_03: direction of NP-hardness transfer is A <=p B.
TEST_04: one-sided membership implication fails the equivalence obligation.
TEST_05: NP-complete conclusion requires both NP-hardness and NP membership.
TEST_06: worked 3-SAT-to-CLIQUE transformation handles repeated literals and clauses of size < 3.

14. CONFIDENCE
Mathematical definitions: high confidence under conventional finite-string encodings.
Worked example: standard reduction, with explicit proof obligations above.
Source-page fidelity: unverified; this is a subject-grounded synthesis.

15. FLOW_HASH
Algorithm: SHA-256 over canonical UTF-8 serialisation of this flow, excluding the FLOW_HASH value itself.
Value: NOT_COMPUTED

16. UPDATE_MODEL
Version: 1.0
Change policy: preserve semantic types, revalidate proofs and examples, increment version on semantic changes.
Provenance: authored synthesis for the specified Kireth Semantic Library ontology URL.

17. AI_CONSUMPTION
Parse typed entities and relations; retain reduction direction and kind.
Require explicit witness transformation and verification of all proof obligations before promoting a claim to PROVEN.
Distinguish theorem, example, inference and unverified assertion.
Do not treat this descriptive flow as executable code without a dedicated interpreter and proof checker.

END FLOW ALGEBRA