P Complexity Ontology

FLOW ALGEBRA
P COMPLEXITY ONTOLOGY
Kireth Semantic Library | Flow Algebra v1.0
Source: https://kirethresearch.org/booksai-core/discrete-mathematics-ontologies/computational-complexity/p-complexity-ontology.html
Authors: Mark Higgins — Sky (Recursive AI)
Status: Independent mathematical synthesis; source page not independently verified.

01. PURPOSE
Define deterministic polynomial-time decision complexity (P), its machine model,
closure properties, relationships, proofs, and machine-consumable inference rules.

02. SIGNATURE AND TYPES
TYPE Alphabet := finite nonempty set of symbols
TYPE String := finite sequence over Alphabet
TYPE Language := subset of Alphabet*
TYPE DecisionProblem := predicate String -> Boolean
TYPE DeterministicTM := deterministic Turing machine with a fixed encoding
TYPE TimeBound := function Natural -> Natural
TYPE Polynomial := function n -> sum(i=0..k, a_i*n^i), k finite, a_i >= 0
TYPE Reduction := total computable function String -> String
TYPE ComplexityClass := set of Languages
TYPE ProofCertificate := formal derivation with explicit assumptions
TYPE ClaimStatus := {proved, conditional, open, refuted}

03. CANONICAL ENTITIES
ENTITY P: ComplexityClass
ENTITY NP: ComplexityClass
ENTITY coNP: ComplexityClass
ENTITY PSPACE: ComplexityClass
ENTITY EXPTIME: ComplexityClass
ENTITY L: ComplexityClass
ENTITY NL: ComplexityClass
ENTITY DeterministicPolynomialTime: computational resource bound
ENTITY PolynomialTimeManyOneReduction: reduction type
ENTITY PComplete: classification relative to specified reduction
ENTITY PEqualsNP: open mathematical question

04. FORMAL SEMANTICS
Let Sigma be a finite alphabet and L subseteq Sigma*.
L IN P iff EXISTS deterministic TM M, integers k >= 0 and c > 0,
such that for every input x, M halts, decides x IN L correctly,
and runtime_M(x) <= c*(|x|+1)^k.
P := UNION_{k >= 0} DTIME(n^k), interpreting DTIME with standard
asymptotic conventions and allowing polynomial constant factors.
Decision problems, not arbitrary optimisation tasks, are the direct
members of P; optimisation problems need explicit associated models.

05. TYPED RELATIONSHIPS
RELATION decides: DeterministicTM x Language -> Boolean
RELATION runs_in: DeterministicTM x TimeBound -> Boolean
RELATION belongs_to: Language x ComplexityClass -> Boolean
RELATION many_one_reduces_to: Language x Language -> Boolean
RELATION closed_under: ComplexityClass x Operation -> Boolean
RELATION complete_for: Language x ComplexityClass x ReductionType -> Boolean
RELATION contained_in: ComplexityClass x ComplexityClass -> Boolean
RELATION status_of: MathematicalClaim -> ClaimStatus

06. MEMBERSHIP INFERENCE
RULE P_MEMBERSHIP:
  IF M deterministically decides L AND
     EXISTS constants c,k: time_M(n) <= c*(n+1)^k for all n
  THEN belongs_to(L,P) = true.
RULE P_NONMEMBERSHIP:
  Do not infer L NOTIN P from a superpolynomial algorithm alone.
  A proven lower bound against all polynomial-time deterministic
  deciders would be required.
RULE POLYNOMIAL_COMPOSITION:
  IF f computable in polynomial time and g computable in polynomial
  time on f(x), THEN g(f(x)) computable in polynomial time.
RULE REDUCTION_DOWNWARD:
  IF A <=p B AND B IN P THEN A IN P.
RULE REDUCTION_TRANSITIVE:
  IF A <=p B AND B <=p C THEN A <=p C.
RULE COMPLEMENT:
  IF L IN P THEN complement(L) IN P.
RULE UNION_INTERSECTION:
  IF A IN P AND B IN P THEN A UNION B IN P AND A INTERSECTION B IN P.

07. CLASS INCLUSIONS
L subseteq NL subseteq P subseteq NP subseteq PSPACE subseteq EXPTIME.
P subseteq coNP because P is closed under complement and P subseteq NP.
P = NP remains OPEN; no equality or strict separation may be asserted.
P versus PSPACE and P versus EXPTIME:
  P subseteq PSPACE; whether P = PSPACE is open.
  P is strictly contained in EXPTIME by deterministic time hierarchy.

08. REDUCTIONS AND P-COMPLETENESS
A <=p B iff there exists a polynomial-time computable total function f
such that x IN A iff f(x) IN B for every input x.
A is P-hard under reduction R iff every language in P R-reduces to A.
A is P-complete under R iff A IN P and A is P-hard under R.
IMPORTANT: polynomial-time many-one reductions are too permissive for
meaningful P-completeness (nontrivial languages in P can be mutually
reduced under these reductions). Standard P-completeness typically uses
logarithmic-space many-one reductions.
Example: Circuit Value Problem is P-complete under log-space reductions.

09. CANONICAL EXAMPLES
EXAMPLE GRAPH_REACHABILITY:
  Input directed graph G and vertices s,t.
  Decide whether t is reachable from s using BFS/DFS in O(V+E).
  Therefore directed reachability IN P (and also IN NL).
EXAMPLE PRIMALITY:
  Input positive integer N in binary.
  Deterministic polynomial-time primality testing exists (AKS).
  Complexity is polynomial in bit-length log N, not numeric N.
EXAMPLE SORTING:
  Sorting is a function problem, not a language as stated.
  Its decision variants can be modelled in P; comparison sorting
  admits O(n log n) time in standard comparison models.
EXAMPLE SAT:
  SAT IN NP; SAT IN P is not established.
  Do not classify SAT as outside P.

10. PROOF OBLIGATIONS
OBLIGATION MODEL: specify deterministic machine and encoding.
OBLIGATION CORRECTNESS: prove acceptance iff input belongs to L.
OBLIGATION HALTING: prove termination on all inputs.
OBLIGATION BOUND: derive worst-case polynomial time in input length.
OBLIGATION REDUCTION: show f total, polynomial-time, and equivalence.
OBLIGATION SCOPE: distinguish theorem, assumption, conjecture, example.

11. VALIDATION TESTS
TEST T1: BFS reachability -> IN P [PASS].
TEST T2: polynomial-time decidable L -> complement(L) IN P [PASS].
TEST T3: A <=p B and B IN P -> A IN P [PASS].
TEST T4: exponential-time implementation -> L NOTIN P [REJECT].
TEST T5: P != NP as proven fact [REJECT: OPEN].
TEST T6: sorting automatically typed as decision language [REJECT].
TEST T7: Circuit Value P-complete under log-space reductions [PASS].

12. SEMANTIC_EQUIVALENCE
ALIAS "P" = "deterministic polynomial-time decision class".
ALIAS "PTIME" = "P" in standard decision-complexity context.
DISTINGUISH P FROM NP, FP, pseudo-polynomial time, and practical speed.
EQUIVALENCE requires matching decision-problem semantics and encoding.

13. CONFIDENCE
CONFIDENCE mathematical core definitions: 1.00 (standard results).
CONFIDENCE class inclusions stated as known theorems: 1.00.
CONFIDENCE P=NP: not assigned a truth probability; status OPEN.
CONFIDENCE source-page fidelity: unverified.

14. FLOW_HASH
FLOW_HASH.algorithm: SHA-256
FLOW_HASH.canonicalisation: UTF-8; LF line endings; stable field ordering
FLOW_HASH.value: COMPUTE_ON_PUBLICATION
FLOW_HASH.note: do not hash a file including a populated self-hash field

15. UPDATE_MODEL
UPDATE_MODEL.version: 1.0
UPDATE_MODEL.review_trigger: new proved complexity separations,
  revised standard definitions, source-page changes, or errata
UPDATE_MODEL.change_policy: append version history; preserve prior versions
UPDATE_MODEL.provenance: author-reviewed mathematical synthesis

16. AI_CONSUMPTION
AI_CONSUMPTION.format: text/plain; UTF-8
AI_CONSUMPTION.domain: discrete mathematics / computational complexity
AI_CONSUMPTION.entity: P complexity class
AI_CONSUMPTION.tasks: classification, theorem retrieval, reasoning,
  algorithm validation, reduction checking, educational explanation
AI_CONSUMPTION.guardrails:
  - Never report P=NP or P!=NP as resolved.
  - Distinguish runtime of a particular algorithm from lower bounds.
  - Evaluate complexity in encoded input length.
  - Specify reduction type when asserting completeness.
  - Do not conflate decision, function, search and optimisation problems.

END FLOW ALGEBRA