P vs NP in Spacetime: Proper-Time Complexity, Curvature-Dependent Trade-Offs, and Conditional Separation Conjectures

Classical complexity theory studies the resources required by algorithms on abstract machines, measuring time by the number of elementary steps. In physical reality, computations are executed by devices embedded in spacetime, with resources bounded by energy, entropy, geometry, and causal structure. We develop a spacetime-aware framework for decision-problem complexity that measures cost in an observer’s proper time and couples it to physically motivated bounds on space (memory), energy, and communication. Within this framework we define relativized complexity classes for polynomial-time and nondeterministic polynomial-time problems that depend on the background spacetime geometry and a resource-mapping function that translates physical resources to logical computational steps. We prove an explicit curvature-independent time-space trade-off inequality by combining the Bekenstein entropy bound with quantum speed limits, show an isometry covariance property of our definitions, and formulate two testable conjectures: (i) a Frame-Dependence Conjecture asserting that, for reasonable families of resource mappings, membership in our proper-time polynomial class can differ between non-coincident observers, and (ii) a Gravitational Acceleration Threshold identifying when polynomial-time solvability measured in a distant coordinate clock emerges from extreme redshift while remaining exponential in local proper time. We contrast these statements with classical complexity theory and with results on closed timelike curves and Malament-Hogarth spacetimes. The resulting program does not claim an absolute resolution of the classical polynomial versus nondeterministic polynomial problem; rather, it proposes a physically explicit reformulation and a suite of falsifiable hypotheses linking computation to spacetime.