Polynomial Time Ontology

FLOW ALGEBRA
POLYNOMIAL TIME ONTOLOGY
Kireth Semantic Library | Version 1.0 | 2026-10-12
Authors: Mark Higgins — Sky (Recursive AI)
Source: https://kirethresearch.org/booksai-core/discrete-mathematics-ontologies/computational-complexity/polynomial-time-ontology.html
Status: Original mathematical synthesis; source page content not independently verified.

1. PURPOSE
Model polynomial-time computation, its formal semantics, complexity relationships, proof obligations and AI-readable inference rules. This specification is declarative: rules describe logical consequences, not a directly executable programming language.

2. TYPED ENTITIES
TYPE Problem = {instances: Set[String], question: String}
TYPE DecisionProblem <: Problem = {answer: Instance -> Boolean}
TYPE Algorithm = {machine: DeterministicMachine, input_encoding: Encoding}
TYPE InputSize = Natural
TYPE RunningTime = Function(Natural, Natural)
TYPE PolynomialBound = {degree: Natural, coefficient: PositiveReal, threshold: Natural}
TYPE ComplexityClass = Set[DecisionProblem]
TYPE Reduction = {source: DecisionProblem, target: DecisionProblem, transform: Function}
TYPE Certificate = FiniteString
TYPE Proof = {premises: Set[Proposition], conclusion: Proposition}
TYPE ResourceMeasure = {kind: TIME | SPACE, model: MachineModel}

3. FORMAL DEFINITIONS
DEF POLYNOMIAL_BOUND(T):
  EXISTS c > 0, k IN Natural, n0 IN Natural:
    FOR ALL n >= n0: T(n) <= c * max(1,n)^k.
DEF POLYNOMIAL_TIME_ALGORITHM(A):
  A is deterministic AND A halts on every input AND
  POLYNOMIAL_BOUND(worst_case_steps(A, input_length)).
DEF P:
  { L subseteq Sigma* | EXISTS deterministic Turing machine M and polynomial p:
      FOR ALL x IN Sigma*: M halts within p(|x|) steps AND
      M accepts x IFF x IN L }.
DEF POLYNOMIAL_MANY_ONE_REDUCTION(A,B):
  EXISTS total polynomial-time computable f:
    FOR ALL x: x IN A IFF f(x) IN B.
DEF P_COMPLETE(L):
  L IN P AND FOR ALL A IN P: A <=_logspace L.
NOTE: P-completeness uses log-space many-one reductions by convention; polynomial-time reductions alone would trivialise hardness among nontrivial languages in P.

4. RELATIONSHIP TYPES
RELATION has_time_bound(Algorithm, RunningTime)
RELATION decides(Algorithm, DecisionProblem)
RELATION belongs_to(DecisionProblem, ComplexityClass)
RELATION reduces_to(DecisionProblem, DecisionProblem)
RELATION bounded_by(RunningTime, PolynomialBound)
RELATION verified_by(Proposition, Proof)
RELATION depends_on(Algorithm, MachineModel)
RELATION contrasts_with(ComplexityClass, ComplexityClass)

5. FLOW RULES
RULE P_MEMBERSHIP:
  IF decides(A,L) AND POLYNOMIAL_TIME_ALGORITHM(A)
  THEN belongs_to(L,P).
RULE TRANSITIVE_REDUCTION:
  IF A <=_p B AND B <=_p C THEN A <=_p C.
RULE DOWNWARD_CLOSURE:
  IF A <=_p B AND B IN P THEN A IN P.
RULE POLYNOMIAL_COMPOSITION:
  IF f and g are total polynomial-time computable functions
  THEN g composed_with f is polynomial-time computable.
RULE P_SUBSET_NP:
  IF L IN P THEN L IN NP.
RULE P_SUBSET_PSPACE:
  IF L IN P THEN L IN PSPACE.
RULE FINITE_POLYNOMIAL_SUM:
  IF T1(n)=O(n^a) AND T2(n)=O(n^b)
  THEN T1(n)+T2(n)=O(n^max(a,b)).
RULE POLYNOMIAL_PRODUCT:
  IF T1(n)=O(n^a) AND T2(n)=O(n^b)
  THEN T1(n)*T2(n)=O(n^(a+b)).

6. COMPLEXITY BOUNDARIES
P concerns deterministic worst-case polynomial time for decision problems.
Polynomial time is defined relative to the length of the chosen finite input encoding.
Standard reasonable deterministic machine models preserve polynomial-time membership under polynomial simulation.
An algorithm that is polynomial in a numeric value can be exponential in its binary input length (pseudo-polynomial time).
Polynomial-time membership is an asymptotic statement; large degrees and constants can still be impractical.
P versus NP remains unresolved. Do not infer P != NP or P = NP.
P subseteq NP subseteq PSPACE subseteq EXPTIME; whether all these containments are strict is not known.
By the deterministic time hierarchy theorem, P is a strict subset of EXPTIME.

7. WORKED EXAMPLES
EXAMPLE GRAPH_REACHABILITY:
  Input: directed graph G=(V,E), vertices s,t.
  Algorithm: breadth-first search from s; accept iff t is visited.
  Time: O(|V|+|E|) with adjacency lists.
  Conclusion: directed s-to-t reachability IN P.
EXAMPLE SORTING:
  Comparison merge sort takes O(n log n) comparisons.
  Sorting is a function problem, not itself a decision language; its polynomial runtime is nevertheless meaningful.
EXAMPLE PRIMALITY:
  Decision problem: is binary-encoded integer N prime?
  Known deterministic polynomial-time algorithms imply PRIMES IN P.
EXAMPLE PSEUDO_POLYNOMIAL:
  A dynamic program taking O(nW) time, where W is binary-encoded,
  is not necessarily polynomial in total input length.
EXAMPLE COMPOSITION:
  f runs in O(n^2) and outputs at most O(n^2) symbols.
  g runs in O(m^3) on inputs of length m.
  Computing g(f(x)) is O(n^2+n^6)=O(n^6).

8. PROOF OBLIGATIONS
OBLIGATION TOTALITY: show termination for every valid input.
OBLIGATION CORRECTNESS: prove accept iff instance belongs to target language.
OBLIGATION COST_MODEL: state machine model and charged operations.
OBLIGATION INPUT_ENCODING: specify finite encoding and bit-length.
OBLIGATION WORST_CASE_BOUND: derive a polynomial bound uniform over all inputs of length n.
OBLIGATION REDUCTION_CORRECTNESS: prove x IN A iff f(x) IN B.
OBLIGATION REDUCTION_RUNTIME: prove transformation f runs in polynomial time.

9. SEMANTIC EQUIVALENCE
ALIAS "polynomial-time decidable" == "belongs to P" FOR decision languages.
ALIAS "efficiently computable" ~= "polynomial-time computable" (informal, context-dependent).
DISTINGUISH "polynomial-time verification" FROM "polynomial-time decision".
DISTINGUISH "polynomial in value" FROM "polynomial in input bit-length".
DISTINGUISH "NP-hard" FROM "not in P"; no unconditional equivalence is known.

10. VALIDATION TESTS
TEST T1: T(n)=3n^3+2n+1 -> POLYNOMIAL_BOUND true.
TEST T2: T(n)=2^n -> POLYNOMIAL_BOUND false.
TEST T3: BFS graph reachability -> P membership true.
TEST T4: binary-encoded W with runtime O(nW) -> no automatic P inference.
TEST T5: A <=_p B AND B IN P -> A IN P.
TEST T6: L IN NP -> L IN P is not a valid general inference.
TEST T7: polynomial-time reduction A <=_p B alone -> cannot establish B NP-hard without hardness premise for A.
TEST T8: log-space many-one completeness proof -> requires both membership in P and P-hardness under log-space reductions.

11. CONFIDENCE
CONFIDENCE.formal_definitions = 1.00
CONFIDENCE.standard_class_inclusions = 1.00
CONFIDENCE.unresolved_P_vs_NP = "OPEN_PROBLEM"
CONFIDENCE.source_page_alignment = "UNVERIFIED"
CONFIDENCE.policy = "Do not replace mathematical proof with a numeric confidence score."

12. FLOW HASH
FLOW_HASH.algorithm = "SHA-256"
FLOW_HASH.canonicalisation = "UTF-8; LF newlines; exclude mutable hash-value field"
FLOW_HASH.value = "NOT_COMPUTED"
FLOW_HASH.purpose = "Integrity check after canonicalisation; not a proof of mathematical correctness"

13. UPDATE MODEL
UPDATE_MODEL.version = "1.0"
UPDATE_MODEL.review_trigger = ["new formal result", "corrected theorem", "ontology schema revision"]
UPDATE_MODEL.change_control = "Record version, date, author, changed assertions and supporting proof"
UPDATE_MODEL.compatibility = "Preserve stable typed identifiers or publish explicit mappings"

14. AI CONSUMPTION
AI_CONSUMPTION.domain = "Discrete Mathematics / Computational Complexity"
AI_CONSUMPTION.primary_entity = "Polynomial Time"
AI_CONSUMPTION.machine_reading = "Typed definitions, implications, examples, validation cases"
AI_CONSUMPTION.reasoning_constraints = [
  "Never assert P=NP or P!=NP as established",
  "Always account for input encoding and worst-case runtime",
  "Do not confuse polynomial-time many-one and log-space reductions",
  "Differentiate decision, search and function problems"
]
AI_CONSUMPTION.provenance = "Kireth Semantic Library; original synthesis"

END FLOW ALGEBRA