Constraining the Algorithmic Landscape: A Constructive Approach to Witness Incompressibility and Uniform Verification Limits
Andrew J Murphy · 2025
We examine structural limits on uniform algorithmic generation of NP witnesses, using a constructive framework grounded in Kolmogorov complexity and classical counting arguments. Within this setting, we isolate dense subsets of NP-complete instances whose valid witnesses are provably Kolmogorov-incompressible beyond a fixed threshold. We show that no deterministic polynomial-time algorithm can uniformly generate witnesses across these subsets without violating standard information-theoretic bounds. This suggests that witness generation for such instances lies fundamentally outside P, even though verification remains efficient. The approach avoids dependence on cryptographic assumptions, circuit lower bounds, or uncomputable constructs, and remains unaffected by relativization, natural proofs, or algebrization. By eliminating a broad class of candidate algorithmic strategies, the framework narrows the plausible space in which P = NP could still hold and offers a tractable new angle on the separation question.