Information Redistribution Under Reductions in NP Search
Using reductions from structured P-matrix violation search to classical NP-complete formulations such as 3-SAT and Subset Sum, we examine the relationship between representational expansion, auxiliary variables, local inferability, and information accessibility. Rather than viewing reductions purely as computational transformations, we interpret them as mechanisms that redistribute hidden witness information across enlarged representations. From this perspective, reductions, gadgets, and auxiliary structures may expose globally encoded witness information to local propagation and inference,…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2605.20236
curl -X POST /api/v1/records/arxiv/2605.20236/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2605.20236/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'