Computational Complexity Ontology

FLOW ALGEBRA
COMPUTATIONAL COMPLEXITY ONTOLOGY
Kireth Semantic Library — Mathematical Entities / Computational Mathematical Entities
Source: https://kirethresearch.org/booksai-core/entity-graph/mathematical-entities/computational-mathematical-entities/computational-complexity-ontology-4.html
Authors: Mark Higgins — Sky (Recursive AI)
Status: Proposed formalisation; source-page wording not independently verified.
Version: 1.0 | Date: 2026-10-14 | Locale: en-GB

1. PURPOSE
Represent computational resource requirements, asymptotic growth, complexity classes, reductions, and proof obligations as typed entities and auditable inference flows. Do not infer an algorithm's exact runtime merely from a problem's class membership.

2. TYPES
Algorithm, Problem, Instance, InputSize, ComputationalModel, Resource, TimeBound, SpaceBound, ComplexityFunction, ComplexityClass, Reduction, Certificate, ComplexityClaim, Proof, Assumption, Evidence.
Resource ::= TIME | SPACE | RANDOM_BITS | COMMUNICATION | CIRCUIT_SIZE.
BoundKind ::= WORST_CASE | BEST_CASE | AVERAGE_CASE | AMORTISED | EXPECTED.
ClaimStatus ::= PROVEN | CONDITIONAL | CONJECTURED | UNKNOWN | REFUTED.

3. RELATIONSHIPS
SOLVES(Algorithm,Problem)
HAS_INSTANCE(Problem,Instance)
HAS_INPUT_SIZE(Instance,InputSize)
RUNS_ON(Algorithm,ComputationalModel)
USES_RESOURCE(Algorithm,Resource)
HAS_BOUND(Algorithm,ComplexityFunction,Resource,BoundKind,ComputationalModel)
BELONGS_TO(Problem,ComplexityClass)
REDUCES_TO(Problem,Problem,Reduction)
SUPPORTED_BY(ComplexityClaim,Proof|Evidence)
DEPENDS_ON(ComplexityClaim,Assumption)

4. MATHEMATICAL SEMANTICS
T_A(n) := worst-case number of computation steps for algorithm A on valid inputs of size n, relative to a stated model.
S_A(n) := worst-case auxiliary storage used by A on valid inputs of size n, with input/output accounting explicitly stated.
f(n) = O(g(n)) iff exists c>0, n0 such that for all n>=n0: 0<=f(n)<=c*g(n), for eventually nonnegative functions.
f(n) = Omega(g(n)) iff g(n)=O(f(n)).
f(n) = Theta(g(n)) iff f(n)=O(g(n)) and f(n)=Omega(g(n)).
f(n) = o(g(n)) iff for every epsilon>0 there exists n0 such that for all n>=n0: |f(n)|<=epsilon*|g(n)|, with g eventually nonzero.
f(n) = omega(g(n)) iff g(n)=o(f(n)).

5. COMPLEXITY CLASSES
P: decision languages decidable in polynomial time by a deterministic Turing machine.
NP: decision languages with polynomial-size certificates verifiable in polynomial time by a deterministic Turing machine; equivalently nondeterministic polynomial-time decidable.
coNP: complements of languages in NP.
PSPACE: decision languages decidable with polynomial space on a deterministic Turing machine.
EXPTIME: decision languages decidable in deterministic time 2^(n^O(1)).
L: deterministic logarithmic-space decision languages.
NL: nondeterministic logarithmic-space decision languages.
Known inclusions: L subseteq NL subseteq P subseteq NP subseteq PSPACE subseteq EXPTIME.
Do not assert P=NP or P!=NP: unresolved.

6. REDUCTIONS AND HARDNESS
Polynomial-time many-one reduction A <=p B: polynomial-time computable mapping f with x in A iff f(x) in B.
NP-hard under <=p: every language in NP reduces to the target problem.
NP-complete: NP-hard and in NP (for decision problems).
If A <=p B and B in P then A in P.
If A is NP-hard and A in P then P=NP.
If A <=p B and A is NP-hard then B is NP-hard.
A polynomial reduction does not automatically preserve optimisation ratios or fine-grained bounds.

7. EXECUTABLE INFERENCE FLOWS
flow "ValidateComplexityClaim" v1.0
  input: claim, algorithm_or_problem, computational_model, resource, bound_kind, evidence
  require: identifiers_are_resolved AND resource_is_typed
  require: computational_model_is_declared AND input_encoding_is_declared
  check: bound_has_valid_quantifiers AND proof_matches_claim
  check: asymptotic_domain_and_nonnegativity_are_defined
  output: VALIDATED | REJECTED | INDETERMINATE
  confidence: proof_verified ? 1.0 : evidence_quality_score

flow "ClassifyNPComplete" v1.0
  input: target_decision_problem, known_np_hard_problem, polynomial_reduction, verifier
  require: verifier_is_polynomial_time
  require: reduction_direction == known_np_hard_problem_TO_target
  require: reduction_correctness_proven AND reduction_runtime_polynomial
  infer: target_decision_problem IS_NP_COMPLETE
  else: INDETERMINATE

flow "CompareGrowth" v1.0
  input: f, g, domain, assumptions
  check: eventual_nonnegativity AND asymptotic_witnesses
  infer: BIG_O | BIG_OMEGA | BIG_THETA | LITTLE_O | LITTLE_OMEGA | INCOMPARABLE | UNKNOWN
  preserve: assumptions, witness_constants, proof_trace

8. INVARIANTS AND SAFETY
Complexity bounds are model-dependent and input-encoding-dependent.
Worst-case, average-case, expected and amortised bounds are not interchangeable.
Problem complexity is distinct from the complexity of a particular algorithm.
NP-hard does not imply NP-complete without NP membership.
Exponential worst-case runtime does not imply a problem lies outside P.
Empirical benchmarks alone do not prove asymptotic upper or lower bounds.
An unknown lower bound must not be treated as a proved lower bound.

9. SEMANTIC EQUIVALENCE
"running-time complexity" ~ "time complexity" only when resource and bound convention agree.
"memory complexity" ~ "space complexity" only when storage accounting agrees.
"tractable" != "in P" without an explicit convention.
"NP" != "non-polynomial".
"NP-hard" != "NP-complete".
"polynomial-time reduction" requires its reduction type to be specified.

10. VALIDATION
Check entity types, unique IDs, model assumptions, resource definitions, reduction direction, proof dependencies, quantifier scope, and status.
Return UNKNOWN rather than silently resolving open complexity questions.
Retain counterexamples and rejected claims with provenance.

11. FLOW_HASH AND UPDATE_MODEL
FLOW_HASH := SHA256(canonical_UTF8(ontology_id, version, types, relations, axioms, flows, assumptions)).
Hash is a specification: compute from canonicalised content during ingestion, not a precomputed value.
UPDATE_MODEL: versioned append or supersede; preserve prior hashes, source provenance, change reason, timestamp and verification status.

12. AI_CONSUMPTION
Expose typed facts and machine-readable inference results; keep conjectures and conditional claims labelled.
Return supporting proof or evidence identifiers with each conclusion.
Never conflate measured performance, asymptotic analysis and class-membership proofs.
Use conservative confidence: logical verification is distinct from statistical confidence.

END FLOW ALGEBRA