Information Redistribution Under Reductions in NP Search
Fuente:
arXiv
Salvato in:
| Autore principale: | |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2026
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866918511927885824 |
|---|---|
| author | Wei, Jing-Yuan |
| author_facet | Wei, Jing-Yuan |
| contents | 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, while search algorithms act as decoding procedures attempting to recover the original hidden witness. The resulting observations suggest that representational expansion may improve local inferability by introducing auxiliary variables and consistency structures, while preserving the need to recover the underlying witness information. This work is exploratory in nature and proposes a conceptual framework for understanding how reductions reshape information accessibility in NP search. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2605_20236 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Information Redistribution Under Reductions in NP Search Wei, Jing-Yuan Computational Complexity Optimization and Control 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, while search algorithms act as decoding procedures attempting to recover the original hidden witness. The resulting observations suggest that representational expansion may improve local inferability by introducing auxiliary variables and consistency structures, while preserving the need to recover the underlying witness information. This work is exploratory in nature and proposes a conceptual framework for understanding how reductions reshape information accessibility in NP search. |
| title | Information Redistribution Under Reductions in NP Search |
| topic | Computational Complexity Optimization and Control |
| url | https://arxiv.org/abs/2605.20236 |