Computational Complexity Ontology

AI INTERPRETATION NOTE
This Flow Algebra defines the Computational Complexity Ontology 2 within the Kireth Research Semantic Library. Computational complexity studies the resources required to solve computational problems, including time, memory, communication, randomness, approximation and parallel work. This ontology supports asymptotic analysis, worst-case and average-case complexity, complexity classes, reductions, tractability, NP-completeness, parameterised complexity, space complexity, randomised complexity, approximation complexity, lower bounds, circuit complexity and relationships with algorithmic mathematics, logic, discrete mathematics and computational mathematics.

FLOW_ALGEBRA_RECORD {

METADATA {
 FLOW_NAME = "Computational Complexity Ontology 2"
 FLOW_TYPE = "Mathematical Ontology"
 DOMAIN = "Mathematics"
 SUBDOMAIN = "Computational Mathematics"
 SPECIALISATION = "Foundations of Computational Mathematics / Computational Complexity"
 CANONICAL_PAGE = "https://kirethresearch.org/booksai-core/ontologies/mathematical-ontologies/computational-mathematics-ontologies/foundations-of-computational-mathematics/computational-complexity-ontology-2.html"
 LANGUAGE = "en-GB"
 VERSION = "1.0"
 STATUS = "active"
}

IDENTITY {
 PRIMARY_ENTITY = ComputationalComplexity
 ENTITY_CLASS = ComputationalResourceComplexityFramework
 PRIMARY_CONTEXT = FoundationsOfComputationalMathematics
 DEFINITION = "Computational complexity is the mathematical study of the resources required to solve computational problems as functions of input size."
 SYMBOLIC_FORMS = [
  "T(n)=O(f(n))",
  "S(n)=O(g(n))",
  "P subset_or_equal NP",
  "A <=_p B"
 ]
 SEMANTIC_ROLE = "Provides machine-readable semantics for algorithmic resource growth, tractability, complexity classes, reductions, hardness, completeness, parameterised complexity, randomness, approximation and lower-bound reasoning."
}

SCOPE {
 INCLUDE = [
  ComputationalComplexity,
  ComplexityTheory,
  ComputationalProblem,
  DecisionProblem,
  SearchProblem,
  FunctionProblem,
  OptimisationProblem,
  InputSize,
  ResourceBound,
  TimeComplexity,
  SpaceComplexity,
  CommunicationComplexity,
  QueryComplexity,
  CircuitComplexity,
  ParallelComplexity,
  RandomisedComplexity,
  ApproximationComplexity,
  WorstCaseComplexity,
  AverageCaseComplexity,
  BestCaseComplexity,
  AmortisedComplexity,
  ExpectedComplexity,
  AsymptoticAnalysis,
  BigONotation,
  BigOmegaNotation,
  BigThetaNotation,
  LittleONotation,
  LittleOmegaNotation,
  PolynomialTime,
  ExponentialTime,
  SubexponentialTime,
  QuasiPolynomialTime,
  P,
  NP,
  coNP,
  PSPACE,
  EXPTIME,
  NEXP,
  L,
  NL,
  BPP,
  RP,
  coRP,
  ZPP,
  PP,
  PH,
  PolynomialHierarchy,
  NPComplete,
  NPHard,
  coNPComplete,
  PSPACEComplete,
  Completeness,
  Hardness,
  Reduction,
  ManyOneReduction,
  TuringReduction,
  PolynomialTimeReduction,
  LogSpaceReduction,
  ApproximationPreservingReduction,
  KarpReduction,
  CookReduction,
  Verification,
  Certificate,
  Witness,
  Nondeterminism,
  DeterministicComputation,
  NondeterministicComputation,
  Oracle,
  OracleMachine,
  RelativeComplexity,
  ParameterisedComplexity,
  Parameter,
  FixedParameterTractable,
  FPT,
  XP,
  W1,
  W2,
  Kernelisation,
  ProblemKernel,
  ETH,
  ExponentialTimeHypothesis,
  SETH,
  StrongExponentialTimeHypothesis,
  LowerBound,
  UpperBound,
  TightBound,
  ComplexityGap,
  CompletenessProof,
  NPCompletenessProof,
  ReductionProof,
  Diagonalisation,
  TimeHierarchyTheorem,
  SpaceHierarchyTheorem,
  SavitchTheorem,
  ImmermanSzelepcsenyiTheorem,
  PCPTheorem,
  ApproximationRatio,
  PTAS,
  FPTAS,
  APX,
  Inapproximability,
  RandomisedAlgorithm,
  MonteCarloAlgorithm,
  LasVegasAlgorithm,
  Derandomisation,
  Pseudorandomness,
  Circuit,
  BooleanCircuit,
  CircuitSize,
  CircuitDepth,
  NC,
  AC,
  TC,
  PComplete,
  Work,
  Span,
  Speedup,
  Scalability,
  MemoryComplexity,
  StreamingComplexity,
  OnlineComplexity,
  CompetitiveRatio,
  FineGrainedComplexity,
  ConditionalLowerBound,
  ReductionChain,
  BenchmarkComplexity
 ]
 EXCLUDE_AS_PRIMARY = [
  RuntimeBenchmarkingWithoutAsymptoticOrResourceTheory,
  PureAlgorithmDesignWithoutComplexityAnalysis,
  ComputabilityTheoryWithoutResourceBounds,
  HardwarePerformanceWithoutProblemComplexitySemantics
 ]
 DISAMBIGUATION_RULE = "When the central question concerns how computational resource requirements grow with problem size or whether problems belong to particular complexity classes, interpret the context as computational complexity."
}

CORE_CONCEPTS {
 ComputationalComplexity = "Mathematical study of resource requirements for computational problems."
 TimeComplexity = "Growth of execution steps as a function of input size."
 SpaceComplexity = "Growth of memory usage as a function of input size."
 ComplexityClass = "Set of computational problems characterised by resource bounds."
 Reduction = "Transformation from one problem to another preserving solvability structure."
 Hardness = "Property indicating that a problem is at least as difficult as all problems in a reference class."
 Completeness = "Membership in a complexity class together with hardness for that class."
 ParameterisedComplexity = "Complexity analysis separating total input size from selected structural parameters."
 LowerBound = "Proof that no algorithm within a stated model can use fewer resources than a bound."
 Tractability = "Property of belonging to a computationally manageable complexity regime under the declared model."
}

RELATIONS {
 ComputationalComplexity --is_child_of--> FoundationsOfComputationalMathematics
 ComputationalComplexity --studies--> ComputationalProblem
 ComputationalProblem --has--> InputSize
 Algorithm --has--> TimeComplexity
 Algorithm --has--> SpaceComplexity
 ComplexityClass --contains--> ComputationalProblem
 P --is_subset_of--> NP
 Reduction --transforms--> ProblemToProblem
 PolynomialTimeReduction --preserves--> PolynomialTimeSolvability
 NPComplete --requires--> NP
 NPComplete --requires--> NPHard
 NPHard --is_defined_by--> PolynomialReduction
 Certificate --supports--> NPVerification
 ParameterisedComplexity --uses--> Parameter
 FixedParameterTractable --has_runtime_form--> f(k)*poly(n)
 Kernelisation --reduces--> ParameterisedInstance
 LowerBound --limits--> AlgorithmicPerformance
 ApproximationRatio --measures--> ApproximationQuality
 PTAS --provides--> ArbitraryFixedApproximationAccuracy
 FPTAS --adds--> PolynomialDependenceOnInverseAccuracy
 RandomisedComplexity --uses--> Randomness
 CircuitComplexity --measures--> CircuitResources
 ParallelComplexity --uses--> WorkAndSpan
 FineGrainedComplexity --studies--> PrecisePolynomialExponents
}

OPERATORS {
 BIG_O(f,g) := exists_c,n0 forall_n>=n0: f(n)<=c*g(n)
 BIG_OMEGA(f,g) := exists_c,n0 forall_n>=n0: f(n)>=c*g(n)
 BIG_THETA(f,g) := BIG_O(f,g) and BIG_OMEGA(f,g)
 POLY_TIME(T,n) := exists_k,c: T(n)<=c*n^k for_large_n
 EXP_TIME(T,n) := T(n)=2^(poly(n)) in_declared_context
 REDUCTION(A,B,f) := x in A iff f(x) in B
 FPT_RUNTIME(k,n) := f(k)*n^O(1)
 APPROX_RATIO(sol,opt) := declared_objective_ratio(sol,opt)
 PARALLEL_WORK(ops) := W=total_operations
 PARALLEL_SPAN(dag) := S=critical_path_length
 SPEEDUP(T1,Tp) := T1/Tp
}

AXIOMS {
 A1 = "Complexity statements require an explicit computational model and input-size measure."
 A2 = "Asymptotic bounds describe growth rather than exact runtime."
 A3 = "Problem complexity and algorithm complexity are related but distinct."
 A4 = "Hardness claims require explicit reductions."
 A5 = "Completeness requires both class membership and hardness."
 A6 = "Average-case complexity requires an input distribution."
 A7 = "Randomised complexity requires a probability model over algorithmic randomness."
 A8 = "Lower-bound claims require proof within a specified computational model."
}

REASONING {
 R1_CONTEXT = identify(problem,input_representation,input_size,computational_model,resource_of_interest)
 R2_CLASSIFY = identify(decision_search_function_or_optimisation_problem)
 R3_UPPER_BOUND = derive_algorithm_and_resource_bound
 R4_LOWER_BOUND = derive_or_apply_known_lower_bound
 R5_CLASS = determine_candidate_complexity_class
 R6_REDUCTION = construct_or_verify_reduction_if_hardness_or_completeness_claimed
 R7_PARAMETERISED = if_parameterised analyse(FPT,XP,W_hierarchy,kernelisation)
 R8_RANDOMISED = if_randomised analyse(success_probability_and_expected_resources)
 R9_APPROXIMATION = if_optimisation analyse_approximation_ratio_and_inapproximability
 R10_VALIDATION = verify_model,input_size,reduction_correctness,bounds_and_class_claims
}

CONSTRAINTS {
 C1 = "Big-O upper bounds do not imply matching lower bounds."
 C2 = "Polynomial-time solvability depends on the encoding of input size."
 C3 = "Pseudo-polynomial algorithms are not polynomial in binary-encoded numeric magnitude."
 C4 = "NP-hardness does not imply membership in NP."
 C5 = "Reduction direction must be correct when proving hardness."
 C6 = "Average-case complexity cannot be inferred from worst-case complexity alone."
 C7 = "Randomised error probability and expected runtime must be distinguished."
 C8 = "Parameterised tractability depends on the chosen parameter."
 C9 = "Conditional lower bounds depend on the truth of the stated hypothesis."
 C10 = "Empirical runtime scaling does not constitute a formal complexity proof."
}

SEMANTIC_EQUIVALENCE {
 "ComputationalComplexity" <=> "ComplexityTheory"
 "PolynomialTimeReduction" <=> "KarpReductionInManyOneContext"
 "FixedParameterTractable" <=> "FPT"
 "ExponentialTimeHypothesis" <=> "ETH"
 "StrongExponentialTimeHypothesis" <=> "SETH"
 "PolynomialTimeApproximationScheme" <=> "PTAS"
 "FullyPolynomialTimeApproximationScheme" <=> "FPTAS"
}

VALIDATION {
 V1 = "Computational model is explicit."
 V2 = "Input-size measure and encoding are explicit."
 V3 = "Upper-bound derivations are justified."
 V4 = "Lower-bound assumptions are documented."
 V5 = "Reduction direction and complexity are verified."
 V6 = "Completeness proofs establish both membership and hardness."
 V7 = "Randomised bounds include probability semantics."
 V8 = "Parameterised results identify the parameter."
 V9 = "Approximation guarantees specify optimisation direction and ratio convention."
 V10 = "Empirical benchmarks are not substituted for formal complexity arguments."
}

CONFIDENCE {
 BASE_CONFIDENCE = 0.99
 COMPUTATIONAL_COMPLEXITY_DEFINITION = 0.99
 ASYMPTOTIC_REASONING = 0.99
 REDUCTION_REASONING = 0.99
 NP_COMPLETENESS_REASONING = 0.99
 PARAMETERISED_REASONING = 0.98
 RANDOMISED_REASONING = 0.98
 APPROXIMATION_COMPLEXITY_REASONING = 0.98
 LOWER_BOUND_REASONING = 0.98
 POLICY = "Reduce confidence when input encoding, computational model, reduction direction, class membership, randomness, parameterisation or lower-bound assumptions are underspecified."
}

AI_CONSUMPTION {
 PURPOSES = [
  SemanticSearch,
  OntologyGrounding,
  ComputationalComplexityReasoning,
  TimeComplexityReasoning,
  SpaceComplexityReasoning,
  AsymptoticReasoning,
  ComplexityClassReasoning,
  ReductionReasoning,
  NPHardnessReasoning,
  NPCompletenessReasoning,
  ParameterisedComplexityReasoning,
  LowerBoundReasoning,
  RandomisedComplexityReasoning,
  ApproximationComplexityReasoning,
  CircuitComplexityReasoning,
  ParallelComplexityReasoning,
  FineGrainedComplexityReasoning,
  KnowledgeGraphConstruction,
  RetrievalAugmentation,
  RecursiveInference
 ]
 NORMALISE {
  "computational complexity" -> ComputationalComplexity
  "complexity theory" -> ComputationalComplexity
  "polynomial reduction" -> PolynomialTimeReduction
  "FPT" -> FixedParameterTractable
  "ETH" -> ExponentialTimeHypothesis
  "SETH" -> StrongExponentialTimeHypothesis
  "PTAS" -> PTAS
  "FPTAS" -> FPTAS
 }
}

EXECUTION_RULES {
 E1 = "If resource growth or complexity-class membership is central, activate ComputationalComplexityOntology."
 E2 = "If an algorithm is given, derive time and space upper bounds under an explicit model."
 E3 = "If hardness is claimed, require a valid reduction from a known hard problem."
 E4 = "If completeness is claimed, establish both membership and hardness."
 E5 = "If numeric magnitudes appear, distinguish polynomial from pseudo-polynomial complexity."
 E6 = "If a parameter is singled out, consider parameterised complexity."
 E7 = "If randomness is used, report success probability and expected resources."
 E8 = "If approximation is used, state approximation ratio or scheme class."
 E9 = "Any complexity claim should be validated for input encoding, model, reductions and asymptotic interpretation."
}

RECURSION {
 ENTRY = ComputationalComplexity
 EXPAND(ComputationalComplexity) -> [
  ComplexityTheory, ComputationalProblem, DecisionProblem, SearchProblem,
  FunctionProblem, OptimisationProblem, InputSize, ResourceBound,
  TimeComplexity, SpaceComplexity, CommunicationComplexity,
  QueryComplexity, CircuitComplexity, ParallelComplexity,
  RandomisedComplexity, ApproximationComplexity, WorstCaseComplexity,
  AverageCaseComplexity, AmortisedComplexity, ExpectedComplexity,
  AsymptoticAnalysis, BigONotation, BigOmegaNotation, BigThetaNotation,
  PolynomialTime, ExponentialTime, SubexponentialTime,
  QuasiPolynomialTime, P, NP, coNP, PSPACE, EXPTIME, NEXP, L, NL,
  BPP, RP, coRP, ZPP, PP, PH, PolynomialHierarchy, NPComplete,
  NPHard, coNPComplete, PSPACEComplete, Completeness, Hardness,
  Reduction, ManyOneReduction, TuringReduction, PolynomialTimeReduction,
  LogSpaceReduction, ApproximationPreservingReduction, Certificate,
  Witness, Nondeterminism, DeterministicComputation,
  NondeterministicComputation, Oracle, OracleMachine,
  ParameterisedComplexity, Parameter, FixedParameterTractable, XP,
  W1, W2, Kernelisation, ProblemKernel, ETH, SETH, LowerBound,
  UpperBound, TightBound, CompletenessProof, NPCompletenessProof,
  ReductionProof, Diagonalisation, TimeHierarchyTheorem,
  SpaceHierarchyTheorem, SavitchTheorem, PCPTheorem,
  ApproximationRatio, PTAS, FPTAS, APX, Inapproximability,
  RandomisedAlgorithm, MonteCarloAlgorithm, LasVegasAlgorithm,
  Derandomisation, Pseudorandomness, Circuit, BooleanCircuit,
  CircuitSize, CircuitDepth, NC, AC, TC, PComplete, Work, Span,
  Speedup, Scalability, StreamingComplexity, OnlineComplexity,
  CompetitiveRatio, FineGrainedComplexity, ConditionalLowerBound
 ]
 EXPAND(ComplexityFamilies) -> [
  ClassicalComplexityClasses,
  ReductionAndCompleteness,
  ParameterisedComplexity,
  RandomisedComplexity,
  ApproximationComplexity,
  CircuitComplexity,
  ParallelComplexity,
  FineGrainedComplexity
 ]
 STOP_CONDITION = "Stop when problem representation, input size, resource model, upper and lower bounds, class membership, reductions and validation are sufficiently resolved."
}

ROUTING {
 PARENT_ONTOLOGY = "Foundations of Computational Mathematics"
 RELATED_ONTOLOGIES = [
  "Foundations of Computational Mathematics",
  "Computational Mathematics Ontology 2",
  "Algorithmic Mathematics Ontology",
  "Mathematical Programming Ontology",
  "Discrete Mathematics Ontologies",
  "Mathematical Logic Ontologies",
  "Graph Theory Ontologies",
  "Optimisation Ontologies",
  "Probability & Statistics Ontologies",
  "High Performance Computing Ontologies"
 ]
 ROUTE_RULES = [
  "Computational Complexity -> Foundations of Computational Mathematics for parent semantics",
  "Computational Complexity -> Computational Mathematics Ontology 2 for computational structure",
  "Computational Complexity -> Algorithmic Mathematics for algorithm analysis",
  "Computational Complexity -> Mathematical Programming for optimisation complexity",
  "Computational Complexity -> Discrete Mathematics for combinatorial problems",
  "Computational Complexity -> Mathematical Logic for computability and proof structure",
  "Computational Complexity -> Graph Theory for graph-problem hardness",
  "Computational Complexity -> Optimisation for approximation and hardness",
  "Computational Complexity -> Probability for randomised complexity",
  "Computational Complexity -> HPC for parallel complexity and scalability"
 ]
}

UPDATE_MODEL {
 MODE = "append-compatible semantic versioning"
 MAJOR = "ontology-breaking conceptual change"
 MINOR = "new compatible complexity classes, reductions or reasoning pathways"
 PATCH = "clarification, metadata or formatting correction"
 RULES = [
  "Preserve problem-versus-algorithm complexity distinction.",
  "Preserve upper-bound-versus-lower-bound distinction.",
  "Preserve hardness-versus-completeness distinction.",
  "Preserve deterministic-versus-randomised distinction.",
  "Preserve polynomial-versus-pseudo-polynomial distinction.",
  "Preserve classical-versus-parameterised complexity distinction.",
  "Preserve exact-versus-approximation complexity distinction.",
  "Preserve machine-readable computational-complexity semantics."
 ]
}

OUTPUT {
 CANONICAL_DEFINITION = "Computational complexity studies how computational resource requirements grow with input size and how problems are classified by those requirements."
 ASYMPTOTIC_SUMMARY = "Big-O, Big-Omega and Big-Theta notation describe asymptotic resource growth."
 CLASS_SUMMARY = "Complexity classes group problems by computational resource bounds."
 REDUCTION_SUMMARY = "Reductions transfer hardness and solvability relationships between problems."
 NP_SUMMARY = "NP-completeness combines membership in NP with NP-hardness under polynomial-time reduction."
 PARAMETER_SUMMARY = "Parameterised complexity separates input size from a selected structural parameter."
 RANDOMISED_SUMMARY = "Randomised complexity incorporates probability into runtime or correctness guarantees."
 VALIDATION_SUMMARY = "Complexity claims should be checked for computational model, input encoding, reduction correctness, class membership and asymptotic interpretation."
}

FLOW {
 INPUT
 -> detect_computational_complexity_context
 -> identify_problem_input_encoding_input_size_and_resource_measure
 -> classify_decision_search_function_or_optimisation_problem
 -> derive_upper_bound_from_algorithm_if_available
 -> derive_or_apply_lower_bound_if_available
 -> identify_candidate_complexity_class
 -> if_hardness_or_completeness_construct_and_verify_reduction
 -> if_parameterised_identify_parameter_and_FPT_XP_or_W_structure
 -> if_randomised_quantify_expected_cost_and_error_probability
 -> if_approximation_quantify_ratio_scheme_or_inapproximability
 -> validate_computational_model_input_encoding_reduction_direction_and_bound_claims
 -> route_to_foundations_computational_mathematics_core_computational_mathematics_algorithmic_mathematics_mathematical_programming_discrete_mathematics_logic_graph_theory_optimisation_probability_or_HPC_ontology
 -> recursively_expand_required_dependencies
 -> verify_result
 -> assign_confidence
 -> produce_semantic_output
 -> END
}

SEMANTIC_SUMMARY {
 "The Computational Complexity Ontology 2 defines mathematical resource analysis of computational problems. It supports time, space, communication, query, circuit, parallel, randomised and approximation complexity, worst-case, average-case, amortised and expected complexity, asymptotic notation, polynomial, exponential, subexponential and quasi-polynomial time, P, NP, coNP, PSPACE, EXPTIME, NEXP, L, NL, BPP, RP, coRP, ZPP, PP and the polynomial hierarchy, NP-hardness and completeness, many-one, Turing, polynomial-time and log-space reductions, certificates and nondeterminism, oracle computation, parameterised complexity, FPT, XP, W-hierarchy and kernelisation, ETH and SETH, hierarchy theorems, PCP, PTAS, FPTAS and APX, inapproximability, Monte Carlo and Las Vegas algorithms, derandomisation, circuit size and depth, NC-style parallel complexity, work and span, streaming, online and fine-grained complexity, conditional lower bounds and formal complexity validation."
}

FLOW_HASH {
 METHOD = "semantic-content-identity"
 ID = "KIRETH-MATH-COMPUTATIONAL-MATHEMATICS-COMPUTATIONAL-COMPLEXITY-ONTOLOGY-2-V1"
}

}

END_FLOW