{"id":"arxiv/2605.00953","url":"https://arxiv.org/abs/2605.00953","tags":["cs.IT","cs.CC","math.OC"],"score":0,"title":"Information Accessibility Limits in Structured NP Search","domain":"cs.IT","source":"arxiv","authors":["Jing-Yuan Wei"],"reviews":0,"subject":"cs.IT","summary":"We study the problem of locating violating principal minors in matrix families lying near the boundary of P-matrices. Rather than viewing this search problem purely through computational complexity, we analyze it from an information-accessibility perspective. We show that, despite strong underlying algebraic structure, the location of a violating subset may remain difficult to infer through local queries. In the sparse-violation regime, local observations typically provide only weak eliminative power, and polynomially many queries accumulate only vanishing mutual information about the hidden…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-05-01","reactions":{}}