Computational Problem Ontology

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

1. PURPOSE
Represent computational problems as typed mathematical entities with explicit instance domains, solution relations, correctness conditions, reductions, resource bounds and machine-checkable verification contracts.

2. ENTITY TYPES
ComputationalProblem := (id, kind, I, O, R, encoding, assumptions)
ProblemInstance := (problem_id, input, input_size)
CandidateSolution := (instance_id, output, witness?)
DecisionProblem := ComputationalProblem where O = {YES, NO}
SearchProblem := ComputationalProblem with witness relation R(x,y)
FunctionProblem := ComputationalProblem with functional solution relation
OptimisationProblem := (I, feasible, objective, direction)
PromiseProblem := (Y, N) where Y intersection N = empty; inputs outside Y union N are unspecified
Algorithm := (input_type, output_type, procedure, resource_model)
Reduction := (source_problem, target_problem, mapping, preservation_proof)
ComplexityBound := (resource, asymptotic_bound, model, case)

3. FORMAL SEMANTICS
For a relation problem P = (I,O,R):
  SOL(P,x) = {y in O | R(x,y)}.
For a decision problem, define L_P = {x in I | answer_P(x) = YES}.
For an optimisation problem, OPT(x) = argmin/argmax {f(x,y) | feasible(x,y)}.
For an algorithm A solving a total function problem P:
  forall x in I: A(x) terminates and R(x,A(x)).
For a partial problem, state the domain of required termination explicitly.
Input size n = |encode(x)| under the declared encoding.

4. TYPED RELATIONSHIPS
HAS_INSTANCE: ComputationalProblem -> ProblemInstance
HAS_INPUT_DOMAIN: ComputationalProblem -> InputDomain
HAS_OUTPUT_DOMAIN: ComputationalProblem -> OutputDomain
HAS_SOLUTION_RELATION: ComputationalProblem -> Relation
SOLVED_BY: ComputationalProblem -> Algorithm
VERIFIED_BY: CandidateSolution -> Verifier
REDUCES_TO: ComputationalProblem -> ComputationalProblem
HAS_COMPLEXITY_BOUND: Algorithm -> ComplexityBound
SPECIALISES: ComputationalProblem -> ComputationalProblem
REQUIRES_ASSUMPTION: Claim -> Assumption

5. AXIOMS AND INVARIANTS
A1: Every instance belongs to its problem's declared input domain.
A2: A valid solution satisfies the declared solution relation.
A3: Decision answers are Boolean, not confidence scores.
A4: Optimisation candidates must be feasible before objective comparison.
A5: Complexity claims must specify an input encoding and computation model.
A6: A polynomial-time many-one reduction f from A to B preserves membership:
    x in L_A iff f(x) in L_B; f must be polynomial-time computable.
A7: A problem being undecidable does not imply every individual instance is unsolvable.
A8: An algorithm's empirical runtime is not, by itself, a proof of asymptotic complexity.

6. INFERENCE FLOWS
flow CLASSIFY_PROBLEM(P):
  if output is Boolean and total: infer DecisionProblem
  if outputs are witnesses satisfying R: infer SearchProblem
  if feasible set and objective specified: infer OptimisationProblem
  if domain restricted to disjoint promised sets: infer PromiseProblem
  preserve multiple compatible classifications where appropriate

flow VERIFY_SOLUTION(P,x,y):
  require x in P.I
  require y in P.O
  evaluate P.R(x,y) using declared semantics
  return VALID / INVALID / UNKNOWN with evidence

flow VERIFY_REDUCTION(A,B,f):
  verify type and totality on A's instance domain
  verify mapping resource bound
  verify YES/NO preservation for all applicable instances
  return VERIFIED only with proof or trusted checker result

flow ANALYSE_COMPLEXITY(A,model):
  derive time T(n) and space S(n) with assumptions
  distinguish worst, average, amortised and best cases
  attach upper/lower/tight bound only when justified
  return claims with provenance and proof obligations

7. SEMANTIC DISTINCTIONS
Problem != Instance: a problem defines a family; an instance is one input.
Problem != Algorithm: the specification differs from its solution method.
Decision != Search: yes/no membership differs from witness construction.
Feasible != Optimal: satisfying constraints does not guarantee optimum.
Polynomial-time verifiable != Polynomial-time solvable: do not conflate NP with P.
Reduction direction matters: A <=p B transfers hardness from A to B.

8. EXAMPLES
SAT: instance Boolean formula phi; answer YES iff some assignment satisfies phi.
Shortest path: instance weighted graph, source and target; output minimum-weight path, subject to declared weight assumptions.
Sorting: instance finite sequence and comparator; output ordered permutation preserving the input multiset.

9. VALIDATION
Check identifier uniqueness; domain/output typing; encoding and size definitions;
solution-relation completeness; termination assumptions; feasibility conditions;
reduction direction; resource-model metadata; proof provenance;
UNKNOWN for unverified or undecidable claims rather than invented certainty.

10. CONFIDENCE AND PROVENANCE
CONFIDENCE := {verified, supported, conjectural, unknown}
Never infer correctness from a confidence score alone.
Track source URL, derivation, version, checker, assumptions and timestamp.

11. SEMANTIC_EQUIVALENCE
Two formulations are equivalent only under a documented bidirectional translation preserving solutions (or yes/no answers) under specified assumptions. Similar names do not establish equivalence.

12. FLOW_HASH AND UPDATE_MODEL
FLOW_HASH := SHA-256(canonical UTF-8 representation of ontology content excluding the hash field itself).
UPDATE_MODEL := immutable version identifier + change log + dependency invalidation + recomputation of hash after changes.

13. AI_CONSUMPTION
Expose typed entities and edges, formal preconditions, explicit uncertainty, proof obligations and provenance. Permit inference only where rules' premises are established. Keep open complexity questions (e.g. P versus NP) unresolved.

END FLOW ALGEBRA