Verifying Control Invariance of H-Polytopes is coNP-Complete

arXiv:2610.36773v1 Announce Type: cross Abstract: We prove that verifying whether an H-polytope is control invariant for a discrete-time linear system with polytopic input constraints is \textsc{coNP}-complete. This establishes a fundamental computational complexity barrier for set-theoretic control. As an immediate consequence, the exact computation of maximal control invariant subsets of H-polytopes is \textsc{coNP}-hard. These hardness results hold regardless of whether the input constraint set is given in H- or V-representation.