Computational Complexity Ontology

FLOW ALGEBRA
COMPUTATIONAL COMPLEXITY ONTOLOGY
Version: 1.0
Source URL: https://kirethresearch.org/booksai-core/discrete-mathematics-ontologies/computational-complexity/computational-complexity-ontology-3.html
Authors: Mark Higgins — Sky (Recursive AI)
Project: Kireth Semantic Library
Status: Formal synthesis; source page not independently verified

1. PURPOSE
Model computational resource requirements, asymptotic bounds, complexity classes, reductions, completeness and hardness claims using typed, auditable relations.

2. TYPES
Problem := DecisionProblem | FunctionProblem | OptimisationProblem | PromiseProblem
Instance := FiniteEncodedInput
Algorithm := DeterministicAlgorithm | NondeterministicAlgorithm | RandomisedAlgorithm
Machine := DeterministicTuringMachine | NondeterministicTuringMachine
Resource := Time | Space | RandomBits | CircuitSize | Communication
Bound := AsymptoticFunction
ComplexityClass := P | NP | coNP | PSPACE | EXPTIME | L | NL | OtherClass
Reduction := ManyOneReduction | TuringReduction | LogSpaceReduction
Claim := MembershipClaim | HardnessClaim | CompletenessClaim | SeparationClaim
Evidence := Proof | Counterexample | ConditionalArgument | OpenProblem

3. TYPED RELATIONS
INSTANCE_OF(Instance, Problem)
SOLVES(Algorithm, Problem)
RUNS_ON(Algorithm, Machine)
CONSUMES(Algorithm, Resource, Bound)
BELONGS_TO(Problem, ComplexityClass)
REDUCES_TO(Problem, Problem, Reduction)
HARD_FOR(Problem, ComplexityClass, Reduction)
COMPLETE_FOR(Problem, ComplexityClass, Reduction)
SUPPORTED_BY(Claim, Evidence)
DEPENDS_ON(Claim, Assumption)

4. MATHEMATICAL SEMANTICS
Let |x| denote encoded input length.
TIME_A(x) := number of computational steps used by A on x.
SPACE_A(x) := maximum number of work-tape cells used by A on x.
T_A(n) := max{TIME_A(x) : |x| = n}, where defined.
S_A(n) := max{SPACE_A(x) : |x| = n}, where defined.
f(n) in O(g(n)) iff exists c > 0, n0 such that for all n >= n0: 0 <= f(n) <= c*g(n).
f(n) in Omega(g(n)) iff g(n) in O(f(n)).
f(n) in Theta(g(n)) iff f(n) in O(g(n)) and f(n) in Omega(g(n)).
PolynomialTime(A) iff exists k >= 0 such that T_A(n) in O(n^k).
PolynomialSpace(A) iff exists k >= 0 such that S_A(n) in O(n^k).

5. CLASS DEFINITIONS
P := decision languages decidable by deterministic Turing machines in polynomial time.
NP := decision languages decidable by nondeterministic Turing machines in polynomial time; equivalently those with polynomial-size certificates verifiable in polynomial time.
coNP := {L : complement(L) in NP}.
PSPACE := decision languages decidable by deterministic Turing machines in polynomial space.
EXPTIME := union over k >= 1 of DTIME(2^(n^k)).
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.
Known equality: NPSPACE = PSPACE (Savitch's theorem, with standard space-constructibility conditions).
Open: P = NP?; NP = coNP?; P = PSPACE?; PSPACE = EXPTIME? (the last is not established by the standard hierarchy theorem).
Known strict separation: P proper subset EXPTIME (deterministic time hierarchy).

6. REDUCTIONS
PolynomialManyOne(A,B) iff exists polynomial-time computable f such that for all x: x in A iff f(x) in B.
If PolynomialManyOne(A,B) and B in P, infer A in P.
If PolynomialManyOne(A,B) and A is NP-hard, infer B is NP-hard.
NPComplete(B) iff B in NP and every language in NP polynomial-many-one reduces to B.
A reduction preserves the selected decision predicate, not necessarily instance size or solution counts.
Specify reduction type for every hardness statement; never silently exchange many-one and Turing reductions.

7. INFERENCE RULES
R1: SOLVES(A,P) and T_A(n) in O(n^k) for fixed k => P in P, provided A is deterministic and correct on all valid inputs.
R2: PolynomialVerifier(P,V) and PolynomialCertificateBound(P) => P in NP.
R3: A <=p B and B <=p C => A <=p C.
R4: A is NP-complete and A <=p B => B is NP-hard.
R5: B in NP and B is NP-hard under polynomial many-one reductions => B is NP-complete.
R6: A <=p B and B in P => A in P.
R7: P in PSPACE and PSPACE subseteq EXPTIME => P in EXPTIME.
R8: A is NP-hard and A in P => P = NP (conditional consequence, not an established equality).
R9: Big-O upper bound alone does not imply matching lower bound or optimality.
R10: Worst-case resource bound does not determine average-case performance without an input distribution.

8. EXAMPLES
EX1: Reachability in a directed graph is in NL; it is NL-complete under appropriate log-space reductions.
EX2: 2-SAT is in P.
EX3: 3-SAT is NP-complete under polynomial-time many-one reductions.
EX4: TQBF is PSPACE-complete under polynomial-time many-one reductions.
EX5: A deterministic comparison sort has O(n log n) worst-case time for mergesort; the comparison sorting lower bound is Omega(n log n) for arbitrary distinct keys.
EX6: Binary search uses O(log n) comparisons on a sorted random-access array; precondition SORTED(input) is mandatory.

9. PROOF OBLIGATIONS
For membership: state input encoding, machine model, correctness, resource measure and asymptotic derivation.
For hardness: identify known hard source, explicit reduction, computability bound and yes/no preservation proof.
For completeness: establish both membership and hardness for the same class and reduction convention.
For separations: cite a proven theorem; mark unresolved conjectures as OPEN rather than TRUE.
For randomised algorithms: state error model, probability threshold and whether complexity is expected or worst-case.

10. SEMANTIC EQUIVALENCE
EQ1: Polynomial-time verifiability with polynomial-size certificates <=> NP membership for decision languages.
EQ2: Polynomial deterministic decidability <=> P membership for decision languages.
EQ3: Theta(g) <=> O(g) AND Omega(g), under nonnegative eventual functions.
NON_EQ1: NP-hard != NP-complete unless NP membership is also shown.
NON_EQ2: Exponential upper bound != exponential lower bound.
NON_EQ3: Polynomial-time solvable != practical for all input sizes.

11. VALIDATION
V1: Every BELONGS_TO assertion references a decision language or explicitly defined extension to another problem type.
V2: Every REDUCES_TO edge carries a reduction type and correctness justification.
V3: Every complexity claim names its machine model and input-size measure.
V4: Every class equality or strict separation is tagged PROVEN, CONDITIONAL or OPEN.
V5: No unsupported inference from worst-case to average-case complexity.
V6: Completeness requires separate membership and hardness evidence.
V7: All examples are checked against assumptions and representation constraints.

12. CONFIDENCE
CONFIDENCE(claim) := VERIFIED | CONDITIONAL | CONJECTURED | UNVERIFIED.
Assign VERIFIED only to claims supported by an accepted proof or independently validated theorem.
Use CONDITIONAL for consequences requiring an unproved premise.
Use CONJECTURED for unresolved class relationships; do not promote them to theorem status.

13. FLOW HASH
FLOW_HASH := SHA256(canonical_utf8(flow_body_without_hash_value)).
Canonicalisation: UTF-8; LF line endings; normalised whitespace; deterministic section order.
Hash value: NOT_COMPUTED (compute after final content freeze).

14. UPDATE MODEL
UPDATE_MODEL.version := 1.0
UPDATE_MODEL.strategy := append_provenance_and_revalidate_dependent_claims
UPDATE_MODEL.triggers := new_theorem | corrected_bound | revised_reduction | changed_encoding | new_reference
UPDATE_MODEL.on_change := recompute_flow_hash; rerun_validation; record_revision

15. AI CONSUMPTION
AI_CONSUMPTION.mode := typed_semantic_reasoning
AI_CONSUMPTION.allowed := classify_problems | verify_reductions | compare_bounds | trace_inference | flag_open_questions
AI_CONSUMPTION.require := proof_status | machine_model | reduction_type | source_provenance
AI_CONSUMPTION.forbid := assert_P_equals_NP_without_proof | conflate_hardness_and_completeness | invent_proof
AI_CONSUMPTION.output := claim + assumptions + derivation + confidence + provenance

END FLOW ALGEBRA