Mathematics Computational Complexity From Rs Complexity Class

Five named classes

Computational complexity theory sorts problems by how much time or memory an algorithm needs as the input grows. The classic classes P, NP, coNP, PSPACE, and EXP are the usual landmarks. The Recognition Science framework's machine-checked library of formal theorems defines a type called ComplexityClass, a discrete record of five named classes, and proves that the count is exactly five.

The proof is a direct computation: the theorem complexityClassCount states that the number of classes equals 5. The library also defines a number dft8Size as 2 to the power 3 and proves it equals 8. These two facts together form a certificate object that bundles the five-class count and the eight-point discrete Fourier transform size.

In Recognition Science, the framework models the P versus NP question as whether recognition cost can be verified in polynomial time. The framework's conjecture is that P is not equal to NP, because NP-complete problems have a cost surface with exponentially many basins where the cost is zero. That conjecture is not proved in the library; it remains a prediction.

What the declaration does not claim is important. It does not prove P versus NP, and it does not define the internal structure of any class beyond naming it. The count of five is a theorem, but the meaning of each class in terms of algorithms is not formalized here. The framework's link between its cost model and classical complexity classes is a modeling choice, not a derived result.

theorem complexityClassCount : Fintype.card ComplexityClass = 5 := by decide

structure ComputationalComplexityCert where
  five_classes : Fintype.card ComplexityClass = 5
  dft_poly : dft8Size = 8

What this page does not claim

P versus NP is not proved by this declaration. The five classes are not given algorithmic definitions in this declaration. The certificate does not establish any inclusion or separation between the classes.

Verify this page

Every tagged claim above names its theorem. To check one yourself rather than trust this page, elaborate the source module with Lean 4 and audit its axiom basis:

$ lake env lean IndisputableMonolith/Mathematics/ComputationalComplexityFromRS.lean
expected axiom basis: [propext, Classical.choice, Quot.sound] (the Lean kernel's standard three; no RS-specific axioms)

A page whose claims cannot be reproduced this way does not ship. In production, every anchor links to the exact declaration in the public source release, and this block carries the build receipt for the page itself.

Derived articles

This page is generated by a question-recursion engine: the questions its answers raise become the next pages. The current agenda, with open targets marked red: