Intrinsic Information Flow in Structureless NP Search
This work identifies an informational origin of exponential search complexity for theoretical computer scientists and complexity theorists, particularly in fully symmetric search regimes.
This paper reinterprets NP witness discovery as an information-acquisition process, where the hidden witness is the sole source of uncertainty. In the 'psocid model' where the witness is accessible only via equality probes, each probe reveals at most O(N/2^N) bits of mutual information, leading to a fundamental mismatch with the Ω(N) bits required for reliable recovery.
We reinterpret NP witness discovery through an information-theoretic lens. Rather than measuring search solely by Turing-machine time, we treat recovery as an information-acquisition process: the hidden witness is the sole source of uncertainty, and identification requires reducing this uncertainty through a rate-limited access interface in the sense of Shannon. To make this perspective explicit, we analyze an extreme regime, the \emph{psocid model}, in which the witness is accessible only via equality probes $[π= w^\star]$ under a uniform, structureless prior. Each probe reveals at most $O(N/2^N)$ bits of mutual information, so polynomially many probes accumulate only $o(1)$ total information. By Fano's inequality, reliable recovery requires $Ω(N)$ bits, creating a fundamental mismatch between required and obtainable information. The psocid setting thus isolates a fully symmetric search regime in which no intermediate computation yields global eliminative leverage, thereby exposing an informational origin of exponential search complexity.