Information Accessibility Limits in Structured NP Search
For researchers studying computational complexity of matrix problems, it reveals a fundamental gap between structural properties and information accessibility.
The paper shows that locating violating principal minors in structured matrix families is information-theoretically hard: any algorithm with polynomially many queries cannot identify the violation with constant success probability.
We study the problem of locating violating principal minors in structured matrix families that lie near the boundary of P-matrices and admit sparse violations under perturbation. Viewing violation search as an information acquisition problem, we show that, despite strong underlying structure, the location of a violation is globally encoded and not accessible through local queries. This leads to an information-theoretic bottleneck: each query reveals only vanishing information about the violating subset, so that polynomially many queries accumulate insufficient information to identify it. Using mutual information and Fano's inequality, we show that any algorithm restricted to polynomially many queries cannot recover the violating subset with constant success probability. Our analysis highlights a fundamental distinction between structure and accessibility: even highly structured problems can be computationally intractable when the information required to locate a solution is not accessible through the available queries.