NP-Hard Ontology

FLOW ALGEBRA
NP-HARD ONTOLOGY
Kireth Semantic Library | Discrete Mathematics Ontologies | Computational Complexity
Version: 1.0
Source URL: https://kirethresearch.org/booksai-core/discrete-mathematics-ontologies/computational-complexity/np-hard-ontology.html
Authors: Mark Higgins — Sky (Recursive AI)
Source status: Independent mathematical synthesis; live webpage not verified.

01. PURPOSE
Represent NP-hardness as a formally typed property of computational problems under a specified reduction notion. Distinguish hardness from membership in NP and from NP-completeness.

02. TYPE SYSTEM
TYPE Problem
TYPE DecisionProblem <: Problem
TYPE SearchProblem <: Problem
TYPE OptimisationProblem <: Problem
TYPE Language <: DecisionProblem
TYPE Instance
TYPE Certificate
TYPE Reduction
TYPE ComplexityClass
TYPE Proof
TYPE Bound
TYPE Encoding
TYPE Assumption

03. CORE ENTITIES
ENTITY NP: ComplexityClass
ENTITY P: ComplexityClass
ENTITY NP_HARD: ProblemProperty
ENTITY NP_COMPLETE: ProblemProperty
ENTITY POLYNOMIAL_MANY_ONE_REDUCTION: ReductionKind
ENTITY POLYNOMIAL_TURING_REDUCTION: ReductionKind
ENTITY SAT: DecisionProblem
ENTITY THREE_SAT: DecisionProblem
ENTITY CLIQUE_DECISION: DecisionProblem
ENTITY TSP_DECISION: DecisionProblem
ENTITY TSP_OPTIMISATION: OptimisationProblem
ENTITY HALTING_PROBLEM: DecisionProblem

04. TYPED RELATIONSHIPS
RELATION is_in: DecisionProblem x ComplexityClass -> Boolean
RELATION reduces_many_one_to: DecisionProblem x DecisionProblem -> Boolean
RELATION reduces_turing_to: Problem x Problem -> Boolean
RELATION is_np_hard_under: Problem x ReductionKind -> Boolean
RELATION is_np_complete_under: DecisionProblem x ReductionKind -> Boolean
RELATION transforms_instance: Reduction x Instance -> Instance
RELATION preserves_yes_answer: Reduction x Instance -> Boolean
RELATION has_polynomial_runtime: Reduction -> Boolean
RELATION proves: Proof x Proposition -> Boolean
RELATION has_encoding: Problem x Encoding -> Boolean

05. FORMAL SEMANTICS
Let Sigma be a finite alphabet. A decision problem is represented by a language L subseteq Sigma*.
A <=_m^p B iff there exists a total polynomial-time computable function f such that
  for every x: x in A iff f(x) in B.
For decision problem H:
  NP_HARD_m(H) iff for every L in NP, L <=_m^p H.
For decision problem C:
  NP_COMPLETE(C) iff C in NP AND NP_HARD_m(C).
The reduction type must be explicit. NP-hardness for optimisation and search problems requires an explicitly specified problem model and appropriate reduction (for example an oracle/Turing reduction or an approximation-preserving reduction).

06. INFERENCE RULES
RULE R1 [Hardness via NP-complete source]
  GIVEN A is NP-complete AND A <=_m^p B
  INFER B is NP-hard under polynomial many-one reductions.
RULE R2 [Transitivity]
  GIVEN A <=_m^p B AND B <=_m^p C
  INFER A <=_m^p C.
RULE R3 [Completeness]
  GIVEN B in NP AND B is NP-hard under <=_m^p
  INFER B is NP-complete.
RULE R4 [Membership cannot be inferred]
  GIVEN B is NP-hard
  DO NOT INFER B in NP.
RULE R5 [Polynomial algorithm consequence]
  GIVEN B is NP-hard under <=_m^p AND B in P
  INFER P = NP.
RULE R6 [Hardness transfer]
  GIVEN A is NP-hard under <=_m^p AND A <=_m^p B
  INFER B is NP-hard under <=_m^p.
RULE R7 [No reverse transfer]
  GIVEN A <=_m^p B AND B is NP-hard
  DO NOT INFER A is NP-hard.

07. PROOF OBLIGATIONS
PO1: Specify source problem and its known NP-hardness or NP-completeness.
PO2: Define target decision problem and input encoding precisely.
PO3: Construct a total polynomial-time mapping f.
PO4: Prove x is a YES-instance of source iff f(x) is a YES-instance of target.
PO5: Prove output size and mapping runtime are polynomial in input length.
PO6: For NP-completeness, separately prove target membership in NP with a polynomial-size certificate and polynomial-time verifier.
PO7: Record the reduction notion and any model assumptions.

08. WORKED EXAMPLE: 3-SAT TO CLIQUE
INPUT: 3-CNF formula phi with m clauses, each containing up to three literal occurrences.
CONSTRUCT: Create one vertex per literal occurrence in each clause.
CONNECT: Add an edge between vertices from different clauses iff their literals are not contradictory.
SET: k = m.
FORWARD: A satisfying assignment selects one true literal per clause; the selected vertices form a clique of size m.
REVERSE: A clique of size m chooses one compatible literal occurrence from each clause; these choices extend to a satisfying assignment.
RUNTIME: The graph construction and edge checks are polynomial in the formula size.
CONCLUSION: 3-SAT <=_m^p CLIQUE, so CLIQUE is NP-hard. CLIQUE is also in NP, hence NP-complete.

09. DISTINCTIONS AND COUNTEREXAMPLES
NP-hard does not mean NP-complete.
NP-hard does not imply decidable.
Under polynomial-time Turing reductions, the halting problem is NP-hard: an oracle deciding halting can decide every decidable NP language. It is undecidable and therefore not in NP.
An NP-hard optimisation problem is not automatically a language in NP; formulate its threshold decision variant before claiming NP-completeness.
The assertion P != NP remains unproved; do not present it as a theorem.

10. COMPUTATIONAL COMPLEXITY
Polynomial reductions preserve the implication that a polynomial-time solution to the target would yield a polynomial-time solution to the source.
NP-hardness alone supplies no unconditional exponential lower bound for every algorithm.
Worst-case hardness is not the same as average-case hardness or practical difficulty on typical instances.
Approximation hardness requires separate approximation-preserving reductions and assumptions.

11. SEMANTIC EQUIVALENCE
SEMANTIC_EQUIVALENCE:
  "NP-hard" <=> "at least as hard as every problem in NP under the declared reduction"
  "NP-complete" <=> "in NP and NP-hard under polynomial many-one reductions" [decision languages]
NON_EQUIVALENCE:
  "NP-hard" != "NP-complete"
  "NP-hard" != "exponential runtime proved"
  "NP-hard" != "undecidable"
  "NP-hard" != "in NP"

12. CONFIDENCE
CONFIDENCE:
  mathematical_definitions: 1.00
  established_example_reductions: 1.00
  source_page_alignment: unverified
  open_problem_claims: explicitly_qualified

13. VALIDATION
TEST V1: NP-complete implies NP-hard -> PASS.
TEST V2: NP-hard implies membership in NP -> REJECT.
TEST V3: Valid many-one reduction preserves YES and NO equivalence -> REQUIRED.
TEST V4: Reduction direction reversed without proof -> REJECT.
TEST V5: P = NP declared proved -> REJECT.
TEST V6: NP-hard optimisation automatically NP-complete -> REJECT.
TEST V7: Claimed NP-complete target lacks verifier proof -> REJECT.
TEST V8: Reduction notion omitted -> FLAG.

14. FLOW HASH
FLOW_HASH:
  method: SHA-256
  input: canonical UTF-8 representation of this flow excluding any populated hash value
  value: COMPUTE_ON_PUBLICATION
  status: not_computed

15. UPDATE MODEL
UPDATE_MODEL:
  version: 1.0
  update_triggers: [formal_definition_revision, reduction_proof_revision, example_revision, source_page_alignment]
  compatibility: preserve typed relations and explicit reduction kinds
  provenance: independent_synthesis
  verification: mathematical_consistency_review_required

16. AI CONSUMPTION
AI_CONSUMPTION:
  domain: computational_complexity
  ontology: np_hard
  entity_resolution: typed
  reasoning: rule_based_with_proof_obligations
  inference_guardrails: [no_unproved_P_vs_NP_claims, no_NP_membership_from_hardness, check_reduction_direction, distinguish_decision_from_optimisation]
  output: [classification, reduction_witness, proof_obligations, confidence, provenance]

END FLOW ALGEBRA