betaFeedback

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 AA and BB of a linear discrete-time system, a polytopic input constraint UU, and a candidate polytope XX, Can we decide in polynomial time whether XX is control invariant?

When the candidate XX 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 P=NP\mathrm{P} = \mathrm{NP}, 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 LL can be reduced to problem KK in polynomial time, then LL is no harder than KK: a solver for KK can be used to solve LL after a suitable input transformation.

Let LL be our target problem and KK a known coNP-complete problem. We define the relevant notions as follows:

  • LL is coNP-hard if every problem in coNP can be reduced to LL. In practice, it suffices to establish a polynomial-time reduction from KK to LL; hardness for the entire class then follows by transitivity, since every problem in coNP already reduces to KK.

  • LL 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 P⊆RnP \subseteq\mathbb{R}^{n} can be represented in two ways [17]:

  1. The halfspace representation, also known as HH-representation, is given by

P={x∈Rn∣Hx≤h},P = \left\{ x \in\mathbb{R}^{n} \mid Hx \le h \right\},

where H∈Rf×nH \in\mathbb{R}^{f \times n} denotes a matrix and h∈Rfh \in\mathbb{R}^{f} a vector. In general, PP is a polyhedron, but if we additionally require that Hx≤0Hx \le0 implies x=0x = 0, the set PP is bounded and, hence, a polytope.

  1. The vertex representation, also known as VV-representation, is given by

P=conv⁡{v1,…,vv}=conv⁡(V),P = \operatorname{conv}\{v_{1}, \ldots, v_{v}\} = \operatorname{conv}(V),

the convex hull of a finite set of given points v1,…,vv∈Rnv_{1}, \ldots, v_{v} \in\mathbb{R}^{n}. These points are often stored as columns of the matrix V=[v1,…,vv]V = [v_{1}, \ldots, v_{v}].

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 PP and a V-polytope QQ, with rational data,

(H,h,V)∈Qf×n×Qf×Qn×v,(H, h, V) \in\mathbb{Q}^{f \times n} \times\mathbb{Q}^{f} \times\mathbb{Q}^{n \times v},

decide whether P⊆QP \subseteq Q.

Theorem 1 [5] The HH-in-VV polytope containment problem is coNP-complete. This hardness remains even when PP 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 PP is restricted to a standard cube can be found in [8].

Control Invariance

Let us consider the discrete-time linear system

x+=Ax+Bu,(1)x^{+} = Ax + Bu, \tag*{(1)}

with state x∈Rnx \in\mathbb{R}^{n}, control u∈Rmu \in\mathbb{R}^{m}, and polytopic control constraint set U⊆RmU \subseteq\mathbb{R}^{m}.

Definition 1 A set X⊆RnX \subseteq\mathbb{R}^{n} is control invariant for System (1) if

∀x∈X, ∃u∈U:Ax+Bu∈X.\forall x \in X,\ \exists u \in U : Ax + Bu \in X.

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 AA and BB, the halfspace representation (H,h)(H, h) of the candidate polytope XX, and the polytopic input constraint UU (in either HH- or VV-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 P=conv⁡(V)P = \operatorname{conv}(V) is control invariant if and only if there exists a matrix U=[U1,…,Uv]∈U×⋯×UU = [U_1,\ldots,U_v] \in\mathbb{U} \times\cdots\times\mathbb{U} and a non-negative matrix Λ∈R+v×v\Lambda\in\mathbb{R}^{v \times v}_{+} with

AV+BU=VΛandΛT1=1with1=(1,…,1)T.AV + BU = V\Lambda\quad\text{and} \quad\Lambda^{\mathsf{T}}\mathbf{1} = \mathbf{1} \quad\text{with} \quad\mathbf{1} = (1,\ldots,1)^{\mathsf{T}}.

Hence, as long as the control constraint set U\mathbb{U} 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 U\mathbb{U} 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 P=[−1,1]nP = [-1,1]^n to be the unit cube, and we set Q=conv⁡(V)Q = \operatorname{conv}(V) to be an arbitrary V-polytope. We consider System (1) with

A=(00I0),B=(0−V),A = \begin{pmatrix} 0 & 0 \\ I & 0 \end{pmatrix}, \qquad B = \begin{pmatrix} 0 \\ -V \end{pmatrix},

and

U={u∈R+m∣1Tu=1}.\mathbb{U} = \{u \in\mathbb{R}^{m}_{+} \mid\mathbf{1}^{\mathsf{T}}u = 1\}.

Now, we claim that the H-polytope X=P×{0}X = P \times\{0\} is control invariant if and only if P⊆QP \subseteq Q. In order to prove this, we start with any p∈Pp \in P and set x=(pT,0)T∈Xx = (p^{\mathsf{T}},0)^{\mathsf{T}} \in X. The successor is

x+=(0p−Vu).x^{+} = \begin{pmatrix} 0 \\ p - Vu \end{pmatrix}.

We claim that XX is control invariant if and only if P⊆QP \subseteq Q. Now, we have x+∈Xx^{+} \in X if and only if p−Vu=0p - Vu = 0, where uu must be an element of the unit simplex U\mathbb{U}. But this means that p=Vup = Vu is a convex combination of the columns of VV. Hence,

∃u∈U: p=Vu⟺p∈Q.\exists u \in\mathbb{U}: \ p = Vu \quad\Longleftrightarrow\quad p \in Q.

In other words, for every p∈Pp \in P, we must have p∈Qp \in Q, which is exactly P⊆QP \subseteq Q. This proves our claim that the H-polytope XX is control invariant if and only if P⊆QP \subseteq Q.

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 U\mathbb{U} used in this reduction is a simplex, which has both a compact H-representation with m+2m + 2 inequalities and a compact V-representation with mm 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 (m>2nm > 2n). This limitation is immaterial: one can append decoupled zero-state dimensions to AA and BB until the state dimension exceeds the input dimension, leaving the dynamics unchanged. Hence, the coNP-hardness result holds even under the restriction m≤nm \leq n.

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

X=P×{0}X = P \times\{0\}

may be replaced by the full-dimensional polytope

Xε=P×[−ε,ε]n,X_{\varepsilon} = P \times[-\varepsilon,\varepsilon]^n,

where ε>0\varepsilon> 0 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 (A,B)(A,B) 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 x∈Xx \in X and a proof that no admissible input u∈Uu \in\mathcal{U} satisfies Ax+Bu∈XAx+Bu \in X. This state xx may be chosen to be a vertex of XX, because the set of states in XX admitting a feasible successor is convex, so if all vertices of XX admit such a successor, then every point of XX would. Now suppose that XX is given in the form

X={x∈Rn∣Hx≤h}.X = \{x \in\mathbb{R}^n \mid Hx \le h\}.

Then, the condition “no u∈Uu \in\mathcal{U} satisfies Ax+Bu∈XAx+Bu \in X” is equivalent to the infeasibility of

H(Ax+Bu)≤h,u∈U.H(Ax+Bu) \le h,\quad u \in\mathcal{U}.

By Farkas’ lemma, infeasibility of this system has a dual certificate λ\lambda (a vector of nonnegative multipliers) of size polynomial in the input data. But a deterministic verifier can check in polynomial time that

  1. x∈Xx \in X by verifying Hx≤hHx \le h; and

  2. the Farkas certificate λ≥0\lambda\ge0 proves that the system H(Ax+Bu)≤h, u∈UH(Ax+Bu) \le h,\ u \in\mathcal{U} 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 (x,λ)(x,\lambda) have polynomial bit-length. This follows from well-known results on rational polyhedra: if the system H(Ax+Bu)≤h, u∈UH(Ax+Bu) \le h,\ u \in\mathcal{U} is infeasible and xx is chosen as a rational vertex of XX, then both xx and the Farkas certificate λ\lambda 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 X⊂RnX \subset\mathbb{R}^n be an admissible polytope given by a rational HH-representation. The function problem of computing the maximal control invariant subset of XX is coNP-hard under polynomial-time Turing reductions, for any exact output representation in which equality with a rational HH-polytope can be decided in polynomial time.

Proof of Corollary 1

Let C(X)C(X) denote the maximal control invariant subset of XX. By definition, XX is control invariant if and only if C(X)=XC(X) = X. If XX is control invariant, then its maximal control invariant subset must be XX itself. Conversely, if C(X)=XC(X) = X, then XX is control invariant because C(X)C(X) is control invariant.

Suppose that an algorithm computes C(X)C(X) 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 XX to be tested in polynomial time, then control invariance of XX can be verified by first computing C(X)C(X) and then checking whether C(X)=XC(X) = X. 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. [1]S. Arora and B. Barak. Computational Complexity: A Modern Approach. Cambridge University Press, New York, 2009.
  2. [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. [3]F. Blanchini. Set invariance in control. Automatica, 35(11):1747–1767, 1999.DOI
  4. [4]F. Blanchini and S. Miani. Set-theoretic methods in control. Systems & Control: Foundations & Applications. Birkhäuser Boston, Inc., Boston, MA, 2015.
  5. [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. [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. [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. [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. [9]L.G. Khachiyan. A polynomial algorithm in linear programming. Doklady Akademii Nauk SSSR, 244(5):1093–1096, 1979.
  10. [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. [11]P. McMullen. The maximum numbers of faces of a convex polytope. Mathematika, 17:179–184, 1971.DOI
  12. [12]J.B. Rawlings, D.Q. Mayne, and M.M. Diehl. Model Predictive Control: Theory and Design. Madison, WI: Nob Hill Publishing, 2015.
  13. [13]A. Schrijver. Theory of Linear and Integer Programming. John Wiley & Sons, Chichester, 1986.
  14. [14]K. Tchón. On generic properties of linear systems: An overview. Kybernetika, 19(6):467–474, 1983.
  15. [15]A.M. Turing. Systems of logic based on ordinals. Proceedings of the London Mathematical Society, 45(1):161–228, 1939.
  16. [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. [17]G.M. Ziegler. Lectures on Polytopes. Springer, 1995.

Paper details

vlnc:W_6xn2sh9v
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 1

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

Not recorded for this paper

View statement
Looking for related papers…
Contents