Computational complexity refined by input uncertainty and structure
On the Computational Complexity of Problems: Formalizing Sensitivity to Uncertainty and Parametric Complexity Classes
Computational Complexity
Summary
Traditional computer science asks if some problems can be solved quickly based only on how big the input is. This paper shows that knowing special features or patterns in the input can make hard problems much easier to solve. The authors introduce a way to measure how sensitive problem-solving time is to uncertainty in the inputs and use that to create new complexity classes that explain when some problems really become easier. This new framework helps explain why some problems have fast solutions under certain conditions and guides the design of reliable algorithms and AI tools.
What this means in practice
- •For software architects: Set guaranteed performance levels in software contracts using structured input properties to reduce runtime uncertainty.
- •For ai systems engineers: Split reasoning and tool use in AI systems based on certifiable input structure to manage computational costs predictably.
A theory result. No direct application yet.
Authors
Yannis Tzitzikas
Abstract
Is the classical question $P \stackrel{?}{=} NP$ the right one for understanding the complexity of real-world computation? Traditional worst-case analysis characterizes complexity solely as a function of input size $n$. Yet tasks whose cost is exponential in general often run in polynomial or even linear time once specific structural constraints or partial inputs are known. For instance, the Partition Problem is solvable in linear time, a constant-time core step following linear-time verification, when its inputs satisfy a simple structural property, although no polynomial-time algorithm is known for it in general; Integer Factorization, by contrast, resists structural knowledge: no checkable property of the input is known to improve on the sub-exponential number-field-sieve bound. Classical worst-case analysis cannot explain this difference, because it collapses a whole spectrum of difficulty into a single pessimistic bound. This paper formally develops a comprehensive parametric and uncertainty-aware framework for computational complexity. We introduce the notion of \emph{Sensitivity to Uncertainty} (SU) and formalize the cost variation $Δ_P(n, K)$ under a given input property $K$; we define the uncertainty-vanishing metric $Ψ(n, K)$ and prove a fundamental \emph{Uncertainty Reduction Theorem} bridging cost variation and input uncertainty; and we introduce the parametric classes $P_U[K]$ and $NP_U[K]$ as a more practical, instance-level foundation, focused on certifiable structure, rather than distributional typicality, that resolves the gap between theoretical complexity and real-world tractability. We further show how the same uncertainty analysis supports practice: it enables deterministic SLA via Design-by-Contract informs tool-use and reasoning splits in agentic AI, and provides an explanation of when quantum computers achieve exponential speedup.