>[!warning] >This content has not been peer reviewed. # Complexity and computation — RRT foundation **Complexity** and **computation** (polynomial scaling, verification vs search, step-count as cost) are the ninth foundational area. They underpin the P vs NP application: Landauer and resolution cost; A2, A3. --- ## I. Classical side - **P, NP:** Polynomial-time solvable vs polynomial-time verifiable; is "finding" ever much harder than "checking"? - **Step-count:** Computation as a sequence of steps; each step has a cost (time, energy). --- ## II. Mapping to RRT / RST | Concept | RRT / RST identity | Application | |:---|:---|:---| | **Step** | Translation; each step costs (Landauer). | A3 (Translation). | | **Verification** | Bounded consistency checks; few steps. | P vs NP: "check" is cheap. | | **Solving** | Search over states; potentially many steps. | P vs NP: "find" can be expensive. | | **Polynomial time** | Workload (step count) bounded by $n^k$; substrate scaling. | A2; finite resolution. | | **Resolution cost** | Cost of maintaining / discovering state; can exceed verification cost. | Landauer; A2. | So: **complexity** (P vs NP) is reframed as asymmetry between resolution cost (solve) and verification cost (check) in the substrate's accounting. --- ## Links - **Foundation index:** [[../Foundation index]] - **P vs NP:** [[P vs NP/P vs NP (RST)]] - **RRT:** [[Relational Resolution Theory (RRT)]] - **Applications Roadmap:** [[../../Applications Roadmap]]