Intrinsic Information Flow in Structureless NP Search
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…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2603.06315
curl -X POST /api/v1/records/arxiv/2603.06315/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2603.06315/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'