Complexity Class Ontology

FLOW ALGEBRA
COMPLEXITY CLASS ONTOLOGY
Kireth Semantic Library | Version 1.0 | 2026-10-12
Source: https://kirethresearch.org/booksai-core/discrete-mathematics-ontologies/computational-complexity/complexity-class-ontology.html
Authors: Mark Higgins — Sky (Recursive AI)
Status: Mathematical synthesis; source webpage not independently verified.

1. PURPOSE
Define computational complexity classes as mathematically specified sets of decision problems, together with resource bounds, machine models, reductions, closure properties and proven class relationships.

2. TYPES
TYPE Alphabet = finite nonempty set of symbols
TYPE String = finite sequence over Alphabet
TYPE Language = subset of Alphabet*
TYPE DecisionProblem = Language
TYPE MachineModel = {DTM, NTM, probabilistic_TM, alternating_TM, circuit_family}
TYPE Resource = {time, space, randomness, alternation, circuit_size, depth}
TYPE Bound = function N -> N
TYPE ComplexityClass = set of DecisionProblem
TYPE Reduction = mapping from instances of one problem to instances of another
TYPE Certificate = finite witness string
TYPE ProofStatus = {theorem, conjecture, open, conditional}

3. FORMAL SEMANTICS
A decision problem is identified with language L subseteq Sigma*.
DTIME(f(n)) = {L | a deterministic Turing machine decides L in O(f(n)) time}.
NTIME(f(n)) = {L | a nondeterministic Turing machine decides L in O(f(n)) time}.
DSPACE(f(n)) = {L | a deterministic Turing machine decides L using O(f(n)) work-tape space}.
NSPACE(f(n)) = {L | a nondeterministic Turing machine decides L using O(f(n)) work-tape space}.
P = union_{k>=1} DTIME(n^k).
NP = union_{k>=1} NTIME(n^k).
PSPACE = union_{k>=1} DSPACE(n^k).
NPSPACE = union_{k>=1} NSPACE(n^k).
EXPTIME = union_{k>=1} DTIME(2^(n^k)).
EXPSPACE = union_{k>=1} DSPACE(2^(n^k)).
L = DSPACE(log n), using the standard read-only input and work-tape convention.
NL = NSPACE(log n).
coNP = {L | complement(L) belongs to NP}.
BPP = languages decided by probabilistic polynomial-time machines with error <= 1/3 on every input.

4. TYPED ENTITIES
ENTITY ComplexityClass(id, name, model, resource, bound, decision_semantics)
ENTITY DecisionProblem(id, alphabet, language_definition)
ENTITY Algorithm(id, machine_model, time_bound, space_bound)
ENTITY Reduction(id, source_problem, target_problem, reduction_type, cost_bound)
ENTITY CompletenessClaim(id, problem, class, hardness_reduction, membership_proof)
ENTITY InclusionClaim(id, subset_class, superset_class, proof_status, citation)
ENTITY OpenQuestion(id, proposition, known_bounds, status)

5. RELATIONSHIPS
RELATION belongs_to(DecisionProblem, ComplexityClass)
RELATION decided_by(DecisionProblem, Algorithm)
RELATION bounded_by(Algorithm, Resource, Bound)
RELATION reduces_to(DecisionProblem, DecisionProblem, Reduction)
RELATION subset_of(ComplexityClass, ComplexityClass)
RELATION complete_for(DecisionProblem, ComplexityClass)
RELATION hard_for(DecisionProblem, ComplexityClass)
RELATION complement_of(DecisionProblem, DecisionProblem)
RELATION depends_on(Claim, Assumption)
RELATION supported_by(Claim, Proof)

6. CLASS RELATIONSHIPS: ESTABLISHED
L subseteq NL subseteq P subseteq NP subseteq PSPACE subseteq EXPTIME subseteq EXPSPACE.
NP subseteq PSPACE follows from polynomial-space verification/search.
NPSPACE = PSPACE by Savitch's theorem.
NL = coNL by Immerman-Szelepcsényi theorem.
P subseteq coNP subseteq PSPACE.
P subseteq BPP subseteq PSPACE.
P != EXPTIME by the deterministic time hierarchy theorem.
PSPACE != EXPSPACE by the deterministic space hierarchy theorem.

7. OPEN QUESTIONS: NEVER ASSERT AS PROVEN
P =? NP is open.
NP =? coNP is open.
P =? PSPACE is open.
NP =? PSPACE is open.
BPP =? P is open.
Record each equality or separation claim with proof_status before inference.

8. REDUCTIONS AND COMPLETENESS
Polynomial-time many-one reduction A <=p B:
  exists polynomial-time computable f such that x in A iff f(x) in B.
If A <=p B and B in P, then A in P.
If A <=p B and B in NP, then A in NP.
B is NP-hard iff every A in NP reduces to B under <=p.
B is NP-complete iff B in NP and B is NP-hard.
SAT is NP-complete (Cook-Levin theorem).
TQBF is PSPACE-complete under polynomial-time many-one reductions.
Completeness claims must specify reduction notion and class membership.

9. FLOW OPERATORS
OP CLASSIFY(problem, machine, resource_bound):
  REQUIRE machine decides problem for all inputs
  VERIFY resource_bound under the specified model
  RETURN justified class membership, proof and assumptions

OP REDUCE(A, B, f):
  VERIFY f total and computable within required resource bound
  VERIFY forall x: x in A iff f(x) in B
  RETURN A <= B with reduction type

OP TRANSFER_MEMBERSHIP(A, B, f, class_C):
  REQUIRE REDUCE(A, B, f) is valid
  REQUIRE B belongs_to class_C
  REQUIRE class_C closed under the reduction type
  INFER A belongs_to class_C

OP VERIFY_COMPLETE(B, C):
  REQUIRE membership proof B in C
  REQUIRE hardness proof forall A in C: A <= B
  RETURN complete_for(B, C)

OP CHECK_CLAIM(claim):
  IF theorem THEN require proof or authoritative theorem reference
  IF open THEN block unqualified true/false assertion
  IF conditional THEN retain assumptions in all downstream inferences

10. INFERENCE RULES
RULE R1: If A <=p B and B <=p C, then A <=p C.
RULE R2: If A <=p B and B in P, then A in P.
RULE R3: If B is NP-hard and B in NP, then B is NP-complete.
RULE R4: If A is NP-complete and A <=p B, then B is NP-hard.
RULE R5: If A is NP-complete and A in P, then P = NP.
RULE R6: If L in P, then L in NP and L in coNP.
RULE R7: If C subseteq D and L in C, then L in D.
RULE R8: A claim marked open cannot be promoted to theorem by transitivity or semantic similarity.

11. WORKED EXAMPLES
EXAMPLE SAT:
  INPUT Boolean formula phi
  QUESTION exists assignment satisfying phi?
  CERTIFICATE satisfying assignment of length polynomial in |phi|
  VERIFY assignment in polynomial time
  CONCLUDE SAT in NP
  COOK_LEVIN gives NP-hardness
  CONCLUDE SAT is NP-complete

EXAMPLE GRAPH_REACHABILITY:
  INPUT directed graph G and vertices s,t
  QUESTION is there a directed path from s to t?
  CONCLUDE problem in NL and NL-complete under log-space many-one reductions

EXAMPLE TQBF:
  INPUT fully quantified Boolean formula
  QUESTION does formula evaluate to true?
  CONCLUDE TQBF is PSPACE-complete

12. SEMANTIC EQUIVALENCE
SEMANTIC_EQUIVALENCE("polynomial-time decidable", "in P") when decision model is standard deterministic TM.
SEMANTIC_EQUIVALENCE("nondeterministic polynomial time", "in NP") for decision languages.
SEMANTIC_EQUIVALENCE("polynomial-space decidable", "in PSPACE") under standard TM conventions.
NOT_EQUIVALENT("NP", "non-polynomial time").
NOT_EQUIVALENT("NP-hard", "NP-complete") without membership in NP.
NOT_EQUIVALENT("worst-case hardness", "every instance is difficult").

13. VALIDATION
ASSERT each class has an explicit model and resource definition.
ASSERT each reduction preserves yes/no answers.
ASSERT each completeness claim includes both membership and hardness.
ASSERT all unproved equalities/separations are marked open or conditional.
ASSERT complexity bounds identify input size and resource measure.
ASSERT deterministic/nondeterministic and time/space distinctions are preserved.
ASSERT source theorem provenance is distinguishable from generated synthesis.

14. CONFIDENCE
CONFIDENCE(formal_definitions) = high, subject to stated model conventions.
CONFIDENCE(standard_inclusions) = high.
CONFIDENCE(open_problem_resolution) = undetermined.
CONFIDENCE(source_page_alignment) = unverified.
Do not use numeric confidence as a substitute for mathematical proof.

15. FLOW_HASH
FLOW_HASH_ALGORITHM = SHA-256
FLOW_HASH_INPUT = canonical UTF-8 text of this file, excluding any embedded hash field
FLOW_HASH_VALUE = calculate upon publication; not fabricated here

16. UPDATE_MODEL
VERSION = 1.0
UPDATE_TRIGGER = corrected theorem, new proven class relationship, revised definition, source-page change
UPDATE_ACTION = review proofs, preserve provenance, increment version, recompute hash
OPEN_QUESTION_POLICY = update only on verified mathematical breakthrough

17. AI_CONSUMPTION
CONTENT_TYPE = text/plain; charset=utf-8
DOMAIN = discrete mathematics / computational complexity
PRIMARY_ENTITY = ComplexityClass
REASONING_MODE = typed, proof-aware, assumption-preserving
OUTPUT_REQUIREMENT = distinguish theorem, conjecture, open question and conditional implication
INTEROPERABILITY = complexity theory, algorithm analysis, formal verification, automated reasoning

END FLOW ALGEBRA