{
  "$type": "site.standard.document",
  "bskyPostRef": {
    "cid": "bafyreiae233xpf4gmug2m5qox5cqnvzftngjkcbf47gpo7rs6gk7g74rgq",
    "uri": "at://did:plc:4rgrdigiftglskeax4wvmsev/app.bsky.feed.post/3mglxlp7pxnj2"
  },
  "coverImage": {
    "$type": "blob",
    "ref": {
      "$link": "bafkreiflo6xt7is6b2iafwghkjahlgggocme5jwjsbeuqqwcywuvjhmszm"
    },
    "mimeType": "image/png",
    "size": 24783
  },
  "path": "/abs/2603.06315v1",
  "publishedAt": "2026-03-09T00:00:00.000Z",
  "site": "https://arxiv.org",
  "tags": [
    "Jing-Yuan Wei"
  ],
  "textContent": "**Authors:** Jing-Yuan Wei\n\nWe 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.",
  "title": "Intrinsic Information Flow in Structureless NP Search"
}