{"id":"arxiv/2603.06315","url":"https://arxiv.org/abs/2603.06315","tags":["math.OC","cs.CC","cs.IT"],"score":0,"title":"Intrinsic Information Flow in Structureless NP Search","domain":"math.OC","source":"arxiv","authors":["Jing-Yuan Wei"],"reviews":0,"subject":"math.OC","summary":"Rather than measuring NP search in terms of Turing-machine time, we reinterpret witness recovery as an information-acquisition process: the hidden witness is the sole source of uncertainty, and identification requires sufficient reduction of 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…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-03-06","reactions":{}}