NP Complexity Ontology

FLOW ALGEBRA
NP COMPLEXITY ONTOLOGY
Kireth Semantic Library | Flow Algebra v1.0
Source: https://kirethresearch.org/booksai-core/discrete-mathematics-ontologies/computational-complexity/np-complexity-ontology.html
Authors: Mark Higgins — Sky (Recursive AI)
Status: mathematical synthesis; source webpage not independently verified

01 | DOMAIN
ontology.id := discrete_mathematics.computational_complexity.np_complexity
ontology.label := "NP Complexity Ontology"
ontology.parent := computational_complexity
ontology.scope := decision problems verifiable in nondeterministic polynomial time

02 | TYPES
TYPE Alphabet := finite nonempty set of symbols
TYPE String := finite sequence over Alphabet
TYPE Language := subset of Alphabet*
TYPE DecisionProblem := Language
TYPE Certificate := String
TYPE Verifier := deterministic algorithm(String, Certificate) -> Boolean
TYPE NDTM := nondeterministic Turing machine
TYPE Polynomial := function n -> nonnegative integer bounded by n^k + c for constants k,c
TYPE Reduction := polynomial-time computable mapping between strings
TYPE ComplexityClass := set of DecisionProblem

03 | CORE DEFINITIONS
NP := { L subseteq Sigma* | exists deterministic polynomial-time verifier V and polynomial p,
        forall x: x in L iff exists y, |y| <= p(|x|) and V(x,y)=TRUE }
NP_NDTM := { L | some nondeterministic TM decides L in polynomial time }
THEOREM: NP = NP_NDTM (standard computational models and encodings)
P := { L | some deterministic TM decides L in polynomial time }
P subseteq NP
NP_HARD(A) := forall L in NP, L <=p A
NP_COMPLETE(A) := (A in NP) AND NP_HARD(A)
NOTE: NP means nondeterministic polynomial time, not non-polynomial time.

04 | TYPED RELATIONSHIPS
DecisionProblem --IS_MEMBER_OF--> ComplexityClass
DecisionProblem --HAS_VERIFIER--> Verifier
Verifier --CHECKS--> Certificate
NDTM --DECIDES--> DecisionProblem
DecisionProblem --REDUCES_TO--> DecisionProblem
DecisionProblem --IS_NP_HARD_IF--> all_NP_problems_reduce_to_it
DecisionProblem --IS_NP_COMPLETE_IF--> in_NP_and_NP_hard
P --IS_SUBCLASS_OF--> NP
NP --IS_SUBCLASS_OF--> PSPACE

05 | VERIFICATION FLOW
INPUT x: String
GUESS y: Certificate where |y| <= p(|x|)
COMPUTE accepted := V(x,y)
ASSERT runtime(V,x,y) <= polynomial(|x|) given |y| <= p(|x|)
RETURN accepted
SEMANTICS: x belongs to L iff at least one valid certificate is accepted.

06 | NONDETERMINISTIC DECISION FLOW
INPUT x
BRANCH nondeterministically over polynomially bounded certificates y
RUN V(x,y)
ACCEPT if any branch accepts
REJECT if every branch rejects
GUARANTEE each branch runs in polynomial time

07 | REDUCTION FLOW
INPUT languages A, B; mapping f
REQUIRE f computable in deterministic polynomial time
REQUIRE forall x: x in A iff f(x) in B
INFER A <=p B
IF A NP-hard AND A <=p B THEN B NP-hard
IF B in NP AND B NP-hard THEN B NP-complete
CAUTION: Reduction direction matters; A <=p B shows B is at least as hard as A.

08 | CLASSICAL EXAMPLES
SAT: Boolean formula satisfiability; NP-complete (Cook-Levin theorem)
3-SAT: 3-CNF satisfiability; NP-complete
CLIQUE: graph contains a clique of size at least k; NP-complete
VERTEX-COVER: graph has vertex cover of size at most k; NP-complete
HAMILTONIAN-CYCLE: graph contains a Hamiltonian cycle; NP-complete
SUBSET-SUM: integers contain a subset summing to target; NP-complete
SHORTEST-PATH-DECISION: path length at most bound (standard nonnegative-weight formulation); in P
PRIMALITY: integer is prime; in P

09 | WORKED CERTIFICATE EXAMPLE: CLIQUE
INPUT G=(V,E), k
CERTIFICATE C subseteq V
VERIFY |C| >= k
VERIFY forall distinct u,v in C: (u,v) in E
ACCEPT iff both conditions hold
BOUND: O(|V|^2) adjacency checks using suitable representation
CONCLUSION: CLIQUE in NP
NOTE: NP-hardness additionally requires a valid reduction from a known NP-hard problem.

10 | FORMAL INFERENCE RULES
RULE NP_VERIFIER:
  IF polynomial_certificate_bound(L,p) AND polynomial_verifier(L,V)
  THEN member(L,NP)
RULE P_TO_NP:
  IF member(L,P) THEN member(L,NP)
RULE NP_HARD_TRANSFER:
  IF np_hard(A) AND poly_reduces(A,B) THEN np_hard(B)
RULE NP_COMPLETE:
  IF member(A,NP) AND np_hard(A) THEN np_complete(A)
RULE NP_COMPLETE_IN_P:
  IF np_complete(A) AND member(A,P) THEN P=NP
RULE P_NE_NP_CONDITIONAL:
  IF P != NP AND np_complete(A) THEN A notin P

11 | COMPLEXITY BOUNDARIES
P subseteq NP subseteq PSPACE subseteq EXPTIME
UNKNOWN: P = NP? (open problem)
UNKNOWN: NP = coNP? (open problem)
DO_NOT_INFER: NP-hard implies NP membership
DO_NOT_INFER: NP-complete means no efficient algorithm exists unconditionally
DO_NOT_INFER: NP means every instance is hard
DO_NOT_INFER: fast verification of an optimisation output implies the optimisation problem is NP-complete
DISTINGUISH: decision formulations versus optimisation and search formulations

12 | PROOF OBLIGATIONS
OBLIGATION 1: define precise input encoding and problem language
OBLIGATION 2: give polynomial bound on certificate length
OBLIGATION 3: prove verifier soundness and completeness
OBLIGATION 4: establish verifier polynomial runtime
OBLIGATION 5: for NP-hardness, construct a polynomial reduction in correct direction
OBLIGATION 6: prove both directions of reduction equivalence
OBLIGATION 7: distinguish established theorems from open conjectures

13 | SEMANTIC EQUIVALENCE
"NP" ~ "nondeterministic polynomial time" [exact, complexity-class context]
"polynomially verifiable" ~ "in NP" [exact, for decision languages with standard encodings]
"NP-complete" != "NP-hard" [NP-complete also requires NP membership]
"NP" != "non-polynomial" [invalid expansion]
"efficiently verifiable" requires explicit polynomial-time model

14 | VALIDATION TESTS
TEST T1: SAT in NP -> PASS
TEST T2: P subseteq NP -> PASS
TEST T3: every NP-hard problem is NP-complete -> FAIL
TEST T4: polynomial reduction transfers NP-hardness forward -> PASS
TEST T5: P != NP is a proven theorem -> FAIL
TEST T6: CLIQUE certificate verifies pairwise adjacency in polynomial time -> PASS
TEST T7: NP-complete problem in P implies P=NP -> PASS

15 | CONFIDENCE
formal_definitions: 1.00 [standard definitions]
classical_theorems: 1.00 [established results]
open_problem_resolution: UNDETERMINED
source_page_alignment: UNVERIFIED

16 | FLOW HASH
FLOW_HASH.algorithm := SHA-256
FLOW_HASH.input := canonical_UTF8(flow_document_excluding_FLOW_HASH_value)
FLOW_HASH.value := COMPUTE_AT_PUBLICATION
FLOW_HASH.note := no hash value asserted without canonicalisation and computation

17 | UPDATE MODEL
version := 1.0
update_policy := append_revision_with_change_log
invariants := [mathematical_soundness, typed_relationships, reduction_direction, open_problem_status]
review_triggers := [new_proven_theorem, corrected_example, changed_ontology_links]

18 | AI CONSUMPTION
machine_readable := true
reasoning_mode := typed_symbolic_inference
recommended_uses := [complexity_classification, proof_assistance, reduction_validation, educational_explanations]
required_cautions := [do_not_claim_P_vs_NP_solved, distinguish_hardness_from_membership, verify_reduction_direction]
provenance := source_URL + authored_synthesis + version

END FLOW ALGEBRA