Paperlane

no. 4 · Wednesday 28 October 2026

Verifying Control Invariance of H-Polytopes is coNP-Complete

Mario Eduardo Villanueva and Boris Houska

math.OC

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.

fields
Optimization and Control
pdf ↗ page arXiv:2610.36773 ↗