Source-linked AI summary
Verifying Control Invariance of H-Polytopes is coNP-Complete
Mario Eduardo Villanueva, Boris Houska
TL;DR
Whether control invariance of an H-polytope can be verified in polynomial time remained an open question, despite an efficient vertex-checking approach for V-polytopes. The paper proves coNP-completeness using a reduction and a certificate argument, establishing hardness for exact maximal-subset computation as well.
Problem
The paper asks whether control invariance of an H-polytope can be decided in polynomial time, a question left open because H-polytopes may have exponentially many vertices.
Source: §1 · p. 1Method
The proof reduces coNP-hard H-in-V containment to control-invariance verification and establishes coNP membership using polynomial-size certificates for no instances.
Source: §3.1 · p. 3, §3.2 · p. 4Results
Control-invariance verification for H-polytopes is coNP-complete, regardless of whether the polytopic input constraint is given in H- or V-representation.
Source: §3 · p. 3Takeaways & Limitations
Exact computation of maximal control-invariant subsets of H-polytopes is coNP-hard, and general verification of H-represented MPC terminal sets is inherently hard.
Source: §4 · p. 4, §5 · p. 5The complexity analysis assumes rational input data, and coNP membership relies on polynomial-bit certificates for rational polyhedra.
Source: §2.3 · p. 2, §3.2 · p. 4
Abstract
from arXiv · showhide
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.
1 Introduction
Control invariant sets support set-theoretic control methods, but whether control invariance of H-polytopes can be verified efficiently remained open. The paper settles this question with a coNP-completeness result.
1 Introduction
- Control invariant sets underpin set-theoretic control methods and serve as terminal regions for recursive feasibility and stability in model predictive control.A set is control invariant when some admissible input keeps every state’s successor inside the set.Source: §1 · p. 1
- For V-polytopes, vertex checks reduce verification to linear programs, whereas H-polytopes may have exponentially many vertices, leaving their verification tractability open.The existing vertex-based approach therefore does not resolve the H-representation case.Source: §1 · p. 1
Contribution
- The paper proves H-polytope control-invariance verification coNP-complete; unless P = NP, no polynomial-time procedure exists, and exact maximal-invariant-subset computation is coNP-hard.The latter hardness follows from the verification result.Source: Contribution · p. 1
2 Preliminaries
The preliminaries define the complexity and polytope-representation concepts used in the paper, then state the control-invariance setting and the tractable V-polytope case.
2.1 Complexity Classes
- A problem is coNP-hard when every coNP problem reduces to it, and coNP-complete when it is both coNP-hard and in coNP.A polynomial-time reduction from a known coNP-complete problem suffices to establish coNP-hardness.Source: §2.1 · pp. 1–2
2.2 Polytope Representations
- An H-representation describes a polytope by halfspace inequalities, while a V-representation describes it as the convex hull of finitely many points.The H-representation is bounded when Hx ≤ 0 implies x = 0.Source: §2.2 · p. 2
- H-in-V containment asks whether an H-polytope lies inside a V-polytope and is coNP-complete, even when the H-polytope is a standard cube.The problem is to decide whether P ⊆ Q.Source: §2.2 · p. 2
2.3 Control Invariance
- The paper considers a discrete-time linear system with state x, control u, and polytopic input constraints, assuming rational input data for complexity analysis.The rationality assumption covers the system matrices, candidate H-polytope, and input constraints, whether represented in H- or V-form.Source: §2.3 · p. 2
- For rational data and a polytopic input set, V-polytope control invariance can be checked in polynomial time using a linear-programming solver.The characterization uses admissible controls at the vertices and a nonnegative convex-combination matrix.Source: §2.3 · p. 3
3 Verification of Control Invariance
The section proves coNP-completeness of H-polytope control-invariance verification through a hardness reduction and polynomially verifiable certificates for no-instances.
3 Verification of Control Invariance
- Theorem 2 establishes coNP-completeness for H-polytope control-invariance verification, with hardness holding for either H- or V-represented input constraints.Source: §3 · p. 3
3.1 Hardness
- The hardness reduction encodes H-in-V containment as invariance: X=P×{0} is invariant exactly when P⊆Q, and uses a simplex input set compactly representable either way.The construction uses P as the unit cube and Q as the convex hull of V's columns.Source: §3.1 · p. 3
- Hardness persists when inputs do not outnumber states, and also under controllability and full-dimensionality assumptions.The reduction can be adjusted with decoupled zero-state dimensions and small rational perturbations.Source: §3.1 · pp. 3–4
3.2 Completeness
- For membership, a no-instance is certified by a vertex without a feasible successor and a polynomial-size Farkas certificate checked in polynomial time.The certificate's polynomial bit-length follows from bounds on rational vertices and Farkas certificates.Source: §3.2 · p. 4
4 Practical Implication
The section shows that exact computation of a maximal control invariant subset is coNP-hard under the stated representation and equality-testing conditions. The proof reduces verification to computing the subset and checking whether it equals the candidate polytope.
4 Practical Implication
- Computing the maximal control invariant subset of a rational H-polytope is coNP-hard under polynomial-time Turing reductions for exact output representations with polynomial-time equality testing.The result applies under Theorem 2's assumptions.Source: §4 · p. 4
4.1 Proof of Corollary 1
- An exact polynomial-time computation algorithm would enable polynomial-time verification by checking whether the computed subset equals X.The reduction uses the equivalence between X being control invariant and C(X) = X.Source: §4.1 · p. 5
5 Conclusion
Verifying control invariance of an H-polytope is coNP-complete, while exact computation of maximal control invariant terminal regions is coNP-hard. These results mark a complexity boundary for general verification and computation without additional structural assumptions.
5 Conclusion
- Verifying control invariance of an H-polytope is coNP-complete, and computing maximal control invariant terminal regions is coNP-hard.In MPC, terminal sets are commonly specified in H-representation and constructed using a precomputed stabilizing control law; general verification procedures for such sets are inherently hard.Source: §5 · p. 5
- The result delineates a sharp complexity boundary between tractable V-polytope verification and intractable H-polytope verification.Source: §5 · p. 5