Exponential Time Ontology

FLOW ALGEBRA
EXPONENTIAL TIME ONTOLOGY
Kireth Semantic Library | Discrete Mathematics Ontologies | Computational Complexity
Version: 1.0
Source URL: https://kirethresearch.org/booksai-core/discrete-mathematics-ontologies/computational-complexity/exponential-time-ontology.html
Authorship: Mark Higgins — Sky (Recursive AI)
Status: Mathematical synthesis; live source page not independently verified.

01. DOMAIN
ontology_id := kireth:ExponentialTimeOntology
subject := Exponential Time Complexity
parent := kireth:ComputationalComplexity
scope := deterministic time bounds, exponential growth, EXPTIME, reductions, and resource analysis

02. TYPED ENTITIES
Algorithm : ComputationalProcedure
DecisionProblem : Language
Input : FiniteString
InputSize : NaturalNumber
TimeFunction : NaturalNumber -> NaturalNumber
Machine : DeterministicTuringMachine
ComplexityClass : Set[DecisionProblem]
Reduction : ComputableMapping
Certificate : FiniteString
ResourceBound : AsymptoticFunction

03. RELATIONSHIPS
HAS_INPUT(Algorithm, Input)
HAS_SIZE(Input, InputSize)
HAS_RUNNING_TIME(Algorithm, TimeFunction)
DECIDES(Machine, DecisionProblem)
BOUNDED_BY(TimeFunction, ResourceBound)
BELONGS_TO(DecisionProblem, ComplexityClass)
REDUCES_TO(DecisionProblem, DecisionProblem)
IS_HARD_FOR(DecisionProblem, ComplexityClass)
IS_COMPLETE_FOR(DecisionProblem, ComplexityClass)

04. FORMAL SEMANTICS
Let n = |x| denote the length of input x.
T_M(n) := max { number_of_steps(M,x) : x in Sigma*, |x| = n }.
TIME(t(n)) := { L : some deterministic Turing machine M decides L
                    and T_M(n) = O(t(n)) }.
EXPTIME := union_{k >= 1} TIME(2^(n^k)).
E := union_{c >= 1} TIME(2^(c*n)).
E subseteq EXPTIME.
Exponential running time example: T(n) = Theta(2^n).
EXPTIME permits 2^(poly(n)), not merely 2^(Theta(n)).

05. ASYMPTOTIC GROWTH
For fixed k > 0 and c > 1: n^k = o(c^n).
For positive constants a,b: a*2^(b*n) = 2^(Theta(n)).
2^(n^2) is in EXPTIME, but is not bounded by 2^(O(n)).
A bound O(2^n) is an upper bound, not a matching lower bound.
A problem being in EXPTIME does not establish EXPTIME-hardness.

06. COMPLEXITY RELATIONS
P subseteq NP subseteq PSPACE subseteq EXPTIME.
P is strictly contained in EXPTIME (deterministic time hierarchy theorem).
Whether P = NP remains open.
Whether PSPACE = EXPTIME remains open.
EXPTIME-complete problems are in EXPTIME and EXPTIME-hard under
specified reductions, commonly polynomial-time many-one reductions.

07. INFERENCE RULES
R1: DECIDES(M,L) and T_M(n) in O(2^(n^k)) for fixed k
    => BELONGS_TO(L,EXPTIME).
R2: BELONGS_TO(A,EXPTIME) and A <=p B and BELONGS_TO(B,EXPTIME)
    does not by itself establish that B is EXPTIME-hard.
R3: IS_HARD_FOR(A,EXPTIME) and BELONGS_TO(A,EXPTIME)
    => IS_COMPLETE_FOR(A,EXPTIME).
R4: A <=p B and IS_HARD_FOR(A,EXPTIME)
    => IS_HARD_FOR(B,EXPTIME).
R5: T(n) = O(n^k) for fixed k => T(n) = 2^(O(n)) for n >= 1.
R6: A problem in EXPTIME may admit faster algorithms;
    membership alone does not certify an exponential lower bound.

08. EXECUTION FLOW
flow ExponentialTimeClassification(problem, algorithm, bound):
  REQUIRE problem is a formally specified decision problem
  REQUIRE algorithm decides problem on every valid input
  DERIVE worst_case_time T(n) in a declared computation model
  VERIFY termination and correctness
  IF exists fixed integer k >= 1 with T(n) in O(2^(n^k)):
      ASSERT problem in EXPTIME
  ELSE:
      RETURN "EXPTIME membership not established by this bound"
  IF independent hardness reduction proof exists:
      ASSERT problem is EXPTIME-hard
      IF problem in EXPTIME: ASSERT problem is EXPTIME-complete
  RETURN claims with proof provenance
end flow

09. WORKED EXAMPLE: SUBSET ENUMERATION
Input: a set S of n items.
Procedure: enumerate all 2^n subsets and test a property
in O(n) time per subset.
T(n) = O(n*2^n).
Therefore T(n) in 2^(O(n)), hence in EXPTIME.
This is a bound for this procedure, not proof that every algorithm
for the underlying problem requires exponential time.

10. WORKED EXAMPLE: RECURSIVE BRANCHING
Recurrence: T(n) = 2*T(n-1) + O(1), T(0) = O(1).
Solution: T(n) = Theta(2^n).
A memoised alternative may avoid duplicate subproblems when the
number of distinct states is polynomial in n.

11. PROOF OBLIGATIONS
PO1: Define input encoding and input length.
PO2: State deterministic machine and cost model.
PO3: Establish correctness on all admissible inputs.
PO4: Prove worst-case time upper bound.
PO5: Identify constants and fixed polynomial exponent.
PO6: For completeness, prove hardness under named reduction type.
PO7: Distinguish algorithmic upper bounds from problem lower bounds.

12. VALIDATION TESTS
TEST polynomial: n^3 in 2^(O(n)) => PASS.
TEST exponential: 2^n in EXPTIME => PASS.
TEST larger exponential: 2^(n^2) in EXPTIME => PASS.
TEST unsupported: membership in EXPTIME implies EXPTIME-hard => FAIL.
TEST unsupported: exponential algorithm proves exponential necessity => FAIL.
TEST separation: P != EXPTIME => PASS.
TEST open status: PSPACE != EXPTIME is established => FAIL.

13. SEMANTIC EQUIVALENCE
"exponential-time algorithm" ~= algorithm with exponential time bound,
  subject to explicit convention about 2^(O(n)) versus 2^(poly(n)).
"EXPTIME" == "EXP" as a standard complexity-class alias.
"E" != "EXPTIME" as definitions; equality is not assumed.
"exponential time" != "EXPTIME-complete".

14. CONFIDENCE
formal_definitions: HIGH
standard_class_inclusions: HIGH
example_bounds: HIGH (given stated assumptions)
page_specific_alignment: UNVERIFIED
Unproved class separations must remain OPEN, never inferred.

15. FLOW HASH
FLOW_HASH.algorithm := SHA-256
FLOW_HASH.input := canonical_UTF8(ontology_id, version, typed_entities,
                                 definitions, relationships, inference_rules)
FLOW_HASH.value := COMPUTE_ON_PUBLICATION
Do not treat a placeholder as a computed digest.

16. UPDATE MODEL
UPDATE_MODEL.version := 1.0
UPDATE_MODEL.strategy := semantic_versioning
UPDATE_MODEL.trigger := corrected proof, new established result,
                        revised terminology, or ontology dependency change
UPDATE_MODEL.require := provenance, change log, validation rerun,
                        recomputed flow hash

17. AI CONSUMPTION
AI_CONSUMPTION.mode := typed_symbolic_reasoning
AI_CONSUMPTION.outputs := membership_claim, complexity_bound,
                          reduction_claim, proof_obligations, confidence
AI_CONSUMPTION.guardrails := preserve quantifiers; distinguish upper/lower
  bounds; do not resolve open complexity questions; require evidence
  for completeness and hardness claims
AI_CONSUMPTION.provenance := source_url + derivation + version

END FLOW ALGEBRA