NP-Complete Ontology

FLOW ALGEBRA
NP-COMPLETE ONTOLOGY
Version: 1.0
Canonical URL: https://kirethresearch.org/booksai-core/discrete-mathematics-ontologies/computational-complexity/np-complete-ontology.html
Authors: Mark Higgins — Sky (Recursive AI)
Publisher: Kireth Research | https://kirethresearch.org
Status: Mathematical synthesis; webpage content not independently verified.

1. PURPOSE
Represent NP-completeness as a typed, checkable theory of decision problems, polynomial-time reductions, verifiers, and conditional complexity consequences.

2. TYPED ENTITIES
DecisionProblem := language L subseteq Sigma* over a finite alphabet Sigma.
Instance := finite encoded string x in Sigma*.
Certificate := finite string y, polynomially bounded in |x|.
Verifier := deterministic algorithm V(x,y) returning accept/reject.
PolynomialReduction := polynomial-time computable mapping f: Sigma* -> Gamma*.
ComplexityClass := set of decision problems defined by computational resource bounds.
NPCompleteProblem := decision problem in NP that is NP-hard under polynomial-time many-one reductions.
NPCompleteProof := membership proof plus hardness proof.

3. FORMAL SEMANTICS
NP(L) iff exists deterministic polynomial-time V and polynomial p such that
  x in L <=> exists y, |y| <= p(|x|) and V(x,y)=accept.
A <=p B iff exists total polynomial-time computable f with
  for every x: x in A <=> f(x) in B.
NP_HARD(B) iff for every A in NP, A <=p B.
NP_COMPLETE(B) iff NP(B) and NP_HARD(B).
P subseteq NP.
Whether P = NP is unresolved.

4. RELATIONSHIPS
INSTANCE_OF(x, L) : x is an encoded input for L.
HAS_CERTIFICATE(x, y) : y witnesses yes-membership in L under V.
VERIFIES(V, x, y) : V accepts (x,y).
REDUCES_TO(A, B, f) : f witnesses A <=p B.
BELONGS_TO(L, NP) : L has a polynomial-time verifier.
IS_NP_HARD(L) : all NP languages reduce to L.
IS_NP_COMPLETE(L) : L is both in NP and NP-hard.

5. INFERENCE RULES
R1: POLY_VERIFIER(L,V,p) => BELONGS_TO(L,NP).
R2: NP_COMPLETE(A) and REDUCES_TO(A,B,f) => NP_HARD(B).
R3: NP_HARD(B) and BELONGS_TO(B,NP) => NP_COMPLETE(B).
R4: REDUCES_TO(A,B,f) and REDUCES_TO(B,C,g)
    => REDUCES_TO(A,C,g o f), with polynomial composition.
R5: NP_COMPLETE(B) and BELONGS_TO(B,P) => P=NP.
R6: P!=NP and NP_COMPLETE(B) => B not in P. (Conditional only.)
R7: REDUCES_TO(A,B,f) and BELONGS_TO(B,P) => BELONGS_TO(A,P).

6. CANONICAL EXAMPLES
SAT: Boolean formula satisfiability; NP-complete (Cook-Levin theorem).
3-SAT: 3-CNF satisfiability; NP-complete.
CLIQUE: Given graph G and integer k, is there a clique of size >= k? NP-complete.
VERTEX-COVER: Given G,k, is there a vertex cover of size <= k? NP-complete.
HAMILTONIAN-CYCLE: Does a finite graph contain a Hamiltonian cycle? NP-complete.
SUBSET-SUM: Given integers and target t, does a subset sum to t? NP-complete for standard binary encodings.
TSP-DECISION: Given weighted complete graph and bound B, is there a tour of cost <= B? NP-complete under standard finite integer/rational encodings.
Note: NP-completeness applies to decision formulations; optimisation versions require separate classification.

7. WORKED PROOF PATTERN: 3-SAT -> CLIQUE
Input: 3-CNF formula with m clauses.
Construct one vertex for each literal occurrence in each clause.
Connect vertices from different clauses only when their literals are non-contradictory.
Set k=m.
If formula is satisfiable, choose one true literal per clause: chosen vertices form a clique of size m.
If graph has a clique of size m, its vertices select one non-conflicting literal per clause, yielding a satisfying assignment.
Construction size and runtime are polynomial in the input length.
Thus 3-SAT <=p CLIQUE. Since CLIQUE is in NP and 3-SAT is NP-complete, CLIQUE is NP-complete.

8. PROOF OBLIGATIONS
O1: State precise decision question and input encoding.
O2: Establish NP membership with polynomial certificate and verifier bounds.
O3: Select a known NP-hard source problem.
O4: Construct reduction in polynomial time.
O5: Prove yes iff yes, in both directions.
O6: Check edge cases and encoded output size.
O7: Conclude hardness and membership separately before NP-completeness.

9. SEMANTIC EQUIVALENCE AND DIFFERENCE
NP-complete = NP-hard AND in NP (under the specified reduction notion).
NP-hard does not imply NP membership or decidability.
NP-complete does not mean no efficient algorithm has been proved possible.
Polynomial-time verification does not imply polynomial-time deterministic solving.
A <=p B expresses that B is at least as hard as A for polynomial-time solvability, not the reverse.

10. VALIDATION TESTS
TEST T1: SAT is in NP and NP-hard => NP-complete. EXPECT pass.
TEST T2: NP-hard alone => NP-complete. EXPECT reject.
TEST T3: If NP-complete L is in P => P=NP. EXPECT pass as implication.
TEST T4: P!=NP is an established theorem. EXPECT reject.
TEST T5: A <=p B and B in P => A in P. EXPECT pass.
TEST T6: A <=p B and A in P => B in P. EXPECT reject.
TEST T7: A polynomial reduction must preserve yes/no membership in both directions. EXPECT pass.

11. CONFIDENCE
Formal definitions and classical NP-completeness examples: HIGH (established mathematical theory).
Any newly claimed reduction or classification: UNVERIFIED until proof checked.
Open P versus NP question: OPEN; do not infer resolution.

12. FLOW_HASH
Model: SHA-256 of canonical UTF-8 serialisation of this flow after excluding the FLOW_HASH value itself.
FLOW_HASH_VALUE: UNCOMPUTED (calculate on publication; do not fabricate).

13. UPDATE_MODEL
Version: 1.0
Update trigger: corrected definitions, new verified reductions, source changes, or proof audits.
On update: increment version, record change log, rerun validation, recompute hash.

14. AI_CONSUMPTION
Input: encoded decision problem, certificates, reductions, and provenance.
Process: type-check -> identify class -> verify membership -> check reduction direction -> audit proof obligations.
Output: classification, supporting proof, uncertainty, and provenance.
Guardrails: distinguish proven facts from assumptions and conjectures; never assert P!=NP or P=NP as settled.

END FLOW ALGEBRA