WorksMathematics
Verifying Control Invariance of H-Polytopes is coNP-Complete
Abstract
We prove that verifying whether an H-polytope is control invariant for a discrete-time linear system with polytopic input constraints is 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 coNP-hard. These hardness results hold regardless of whether the input constraint set is given in H- or V-representation.
Introduction
A set is control invariant if, starting from every state in it, some admissible control input keeps the successor state inside the set. The notion originated in the theory of control invariant subspaces [2, 16]. Control invariant sets are the foundation for a wide variety of set-theoretic methods in control, as surveyed in [3, 4, 7]. For example, in model predictive control, they serve as terminal regions to guarantee recursive feasibility and stability [10, 12].
Note that this paper makes no attempt to survey the extensive literature on computing control invariant sets. This is because we ask a much more fundamental question: Given the system matrices and of a linear discrete-time system, a polytopic input constraint , and a candidate polytope , Can we decide in polynomial time whether is control invariant?
When the candidate is a V-polytope—that is, given by its vertices—verification is easy. Namely, Gutman and Cwikel [6] showed that it suffices to check the control invariance conditions at the vertices of the given candidate polytope, reducing the problem to a set of linear programs [9]. For H-polytopes—specified by halfspace inequalities—their approach is, however, not viable. This is because a polytope in halfspace representation may have exponentially many vertices [11]. Therefore, the question of whether verification of control invariance of H-polytopes is tractable has remained wide open.
Contribution
In this paper, we settle the above open question by proving that verifying control invariance of an H-polytope is coNP-complete, see Theorem 2. Consequently, unless , no polynomial-time verification procedure exists for the general problem. The hardness result extends immediately to exact computation of maximal control invariant subsets of given H-polytopes, see Corollary 1.
Preliminaries
This section briefly reviews complexity classes, polytope representations, and the concept of control invariance.
Complexity Classes
A decision problem is in coNP if its “no” instances have polynomial-time verifiable certificates; equivalently, its complement is in NP [1]. To compare the difficulty of problems, we rely on polynomial-time reductions. Intuitively, if problem can be reduced to problem in polynomial time, then is no harder than : a solver for can be used to solve after a suitable input transformation.
Let be our target problem and a known coNP-complete problem. We define the relevant notions as follows:
is coNP-hard if every problem in coNP can be reduced to . In practice, it suffices to establish a polynomial-time reduction from to ; hardness for the entire class then follows by transitivity, since every problem in coNP already reduces to .
is coNP-complete if it is both coNP-hard and belongs to coNP.
Note that while “no” instances in coNP admit easily verifiable certificates, this does not imply that these problems are easy to solve; the intrinsic difficulty lies in discovering such a certificate or proving its absence. This is why both coNP-complete and coNP-hard problems are widely believed to be intractable.
Polytope Representations
A polytope can be represented in two ways [17]:
The halfspace representation, also known as -representation, is given by
where denotes a matrix and a vector. In general, is a polyhedron, but if we additionally require that implies , the set is bounded and, hence, a polytope.
The vertex representation, also known as -representation, is given by
the convex hull of a finite set of given points . These points are often stored as columns of the matrix .
The polytope containment problem asks whether one polytope is contained in another. Of particular interest is the H-in-V containment problem: given an H-polytope and a V-polytope , with rational data,
decide whether .
Theorem 1 [5] The -in- polytope containment problem is coNP-complete. This hardness remains even when is restricted to be a standard cube.
Note that the statement of the above theorem is an immediate consequence of [5 Thm. 1]. The case that is restricted to a standard cube can be found in [8].
Control Invariance
Let us consider the discrete-time linear system
with state , control , and polytopic control constraint set .
Definition 1 A set is control invariant for System (1) if
Throughout this paper, we introduce the following standard convention [13].
Assumption 1 (Input Data) Following the standard convention in computational complexity, we assume that all input data—the matrices and , the halfspace representation of the candidate polytope , and the polytopic input constraint (in either - or -representation)—have rational entries. This is a technical requirement that allows the formal definition of input size and polynomial-time reductions. The geometric results, however, naturally extend to real-valued data.
Given the above convention, the classical result by Gutman and Cwikel [6] states that deciding whether a V-polytope is control invariant can be done in polynomial time. Namely, the V-polytope is control invariant if and only if there exists a matrix and a non-negative matrix with
Hence, as long as the control constraint set is a given polytope and all data is rational, the above condition can be checked in polynomial time by using an LP solver [9]; see also [4, 7].
Verification of Control Invariance
This section establishes the main complexity-theoretic result of the paper, which relies on the input data convention from Assumption 1.
Theorem 2. The problem of verifying whether an H-polytope is control invariant for a discrete-time linear system with polytopic input constraints is coNP-complete. The hardness result holds regardless of whether the input constraint set is specified in H- or V-representation.
The proof proceeds in two steps. We first establish coNP-hardness by a polynomial-time reduction from the H-in-V polytope containment problem. We then show membership in coNP by providing a succinct certificate for “no” instances.
Hardness
In order to construct a reduction from the H-in-V polytope containment problem, we set to be the unit cube, and we set to be an arbitrary V-polytope. We consider System (1) with
and
Now, we claim that the H-polytope is control invariant if and only if . In order to prove this, we start with any and set . The successor is
We claim that is control invariant if and only if . Now, we have if and only if , where must be an element of the unit simplex . But this means that is a convex combination of the columns of . Hence,
In other words, for every , we must have , which is exactly . This proves our claim that the H-polytope is control invariant if and only if .
Thus, a polynomial-time algorithm for verifying control invariance of H-polytopes would imply a polynomial-time algorithm for the H-in-V containment problem, which is coNP-hard. Moreover, the input constraint set used in this reduction is a simplex, which has both a compact H-representation with inequalities and a compact V-representation with vertices. Hence, the reduction can be carried out in polynomial time regardless of whether the input constraint set is specified in H- or V-representation. This establishes coNP-hardness of the control invariance verification problem.
Remark 1. The above reduction may allow more inputs than states (). This limitation is immaterial: one can append decoupled zero-state dimensions to and until the state dimension exceeds the input dimension, leaving the dynamics unchanged. Hence, the coNP-hardness result holds even under the restriction .
Remark 2. The above reduction may produce a non-controllable system and a lower-dimensional candidate set. Neither restriction is essential. Standard perturbation arguments for rational polyhedra imply that the slice
may be replaced by the full-dimensional polytope
where is a sufficiently small rational number, without changing the outcome of the reduction [13]. Likewise, since controllability is an open and dense property of linear systems [14], the pair may be perturbed by an arbitrarily small rational amount to obtain a controllable system while preserving the reduction. Hence, the coNP-hardness result remains valid even under the additional assumptions of controllability and full-dimensionality.
Completeness
It remains to show that the problem lies in coNP. For a “no” instance, a succinct certificate consists of a state and a proof that no admissible input satisfies . This state may be chosen to be a vertex of , because the set of states in admitting a feasible successor is convex, so if all vertices of admit such a successor, then every point of would. Now suppose that is given in the form
Then, the condition “no satisfies ” is equivalent to the infeasibility of
By Farkas’ lemma, infeasibility of this system has a dual certificate (a vector of nonnegative multipliers) of size polynomial in the input data. But a deterministic verifier can check in polynomial time that
by verifying ; and
the Farkas certificate proves that the system has no solution [13].
This is because both checks consist of linear algebra operations (matrix-vector multiplications and comparisons) and are therefore polynomial-time computable.
Hence, every “no” instance admits a polynomial-size certificate that can be verified in polynomial time. Therefore, the control invariance verification problem is in coNP. Together with the hardness result from the previous subsection, this completes the proof of Theorem 2.
Remark 3. The above coNP membership proof relies on the standard assumption that the certificate have polynomial bit-length. This follows from well-known results on rational polyhedra: if the system is infeasible and is chosen as a rational vertex of , then both and the Farkas certificate have numerators and denominators bounded by determinants of submatrices of the input data [13]. Hence, the certificate size is polynomial in the input size.
Practical Implication
The complexity result of Theorem 2 has immediate implications for the computation of maximal control invariant sets. In particular, the hardness of verifying control invariance transfers directly to any exact procedure for computing the maximal control invariant subset of a prescribed admissible polytope, under polynomial-time Turing reductions [1, 15].
Corollary 1. Suppose that the assumptions of Theorem 2 hold, and let be an admissible polytope given by a rational -representation. The function problem of computing the maximal control invariant subset of is coNP-hard under polynomial-time Turing reductions, for any exact output representation in which equality with a rational -polytope can be decided in polynomial time.
Proof of Corollary 1
Let denote the maximal control invariant subset of . By definition, is control invariant if and only if . If is control invariant, then its maximal control invariant subset must be itself. Conversely, if , then is control invariant because is control invariant.
Suppose that an algorithm computes exactly, for every instance in the problem class considered in Theorem 2, in time polynomial in the input size. If its output representation permits equality with to be tested in polynomial time, then control invariance of can be verified by first computing and then checking whether . This gives a polynomial-time Turing reduction from the coNP-hard control-invariance verification problem to the exact computation of the maximal control invariant subset. Hence, the latter function problem is coNP-hard under polynomial-time reductions.
Conclusion
We have proven that verifying control invariance of an H-polytope is coNP-complete. This result delineates a sharp complexity boundary between the tractable V-polytope case and the intractable H-polytope case. In model predictive control, where terminal sets are commonly specified in H-representation and constructed using a precomputed stabilizing control law, our result implies that any general verification procedure for such sets is inherently hard. Moreover, Corollary 1 implies that computing maximal control invariant terminal regions is coNP-hard. This establishes a fundamental limit on what can be achieved without additional structural assumptions.
References
- [1]S. Arora and B. Barak. Computational Complexity: A Modern Approach. Cambridge University Press, New York, 2009.
- [2]G. Basile and G. Marro. Controlled and conditioned invariant subspaces in linear system theory. Journal of Optimization Theory and Applications, 3(5):306–315, 1969.
- [3]F. Blanchini. Set invariance in control. Automatica, 35(11):1747–1767, 1999.DOI
- [4]F. Blanchini and S. Miani. Set-theoretic methods in control. Systems & Control: Foundations & Applications. Birkhäuser Boston, Inc., Boston, MA, 2015.
- [5]R.M. Freund and J.B. Orlin. On the complexity of four polyhedral set containment problems. Mathematical Programming, 33(2):139–145, 1985.DOI
- [6]P.O. Gutman and M. Cwikel. Admissible sets and feedback control for discrete-time linear dynamical systems with bounded controls and states. IEEE Transactions on Automatic Control, 31(4):373–376, 1986.
- [7]B. Houska, M.A. Müller, and M.E. Villanueva. Polyhedral control design: Theory and methods. Annual Reviews in Control, 60:100992, 2025.arxiv.org/abs/2412.13082
- [8]K. Kellner and T. Theobald. Sum of squares certificates for containment of H-polytopes in V-polytopes. SIAM Journal on Discrete Mathematics, 30(2):763–776, 2016.
- [9]L.G. Khachiyan. A polynomial algorithm in linear programming. Doklady Akademii Nauk SSSR, 244(5):1093–1096, 1979.
- [10]D.Q. Mayne, J.B. Rawlings, C.V. Rao, and P.O.M. Scokaert. Constrained model predictive control: Stability and optimality. Automatica, 36(6):789–814, 2000.DOI
- [11]P. McMullen. The maximum numbers of faces of a convex polytope. Mathematika, 17:179–184, 1971.DOI
- [12]J.B. Rawlings, D.Q. Mayne, and M.M. Diehl. Model Predictive Control: Theory and Design. Madison, WI: Nob Hill Publishing, 2015.
- [13]A. Schrijver. Theory of Linear and Integer Programming. John Wiley & Sons, Chichester, 1986.
- [14]K. Tchón. On generic properties of linear systems: An overview. Kybernetika, 19(6):467–474, 1983.
- [15]A.M. Turing. Systems of logic based on ordinals. Proceedings of the London Mathematical Society, 45(1):161–228, 1939.
- [16]W.M. Wonham and A.S. Morse. Decoupling and pole assignment in linear multivariable systems: A geometric approach. SIAM Journal on Control, 8(1):1–18, 1970.DOI
- [17]G.M. Ziegler. Lectures on Polytopes. Springer, 1995.