Skip to content
DraconiticResearch
Search Sources API
203,948 studies31 sourcesUpdated 14 min ago
PreprintCC BY 4.0arXiv

Verifying Control Invariance of H-Polytopes is coNP-Complete

  • Mario Eduardo Villanueva
  • Boris Houska
Open at sourcePDFDOICite

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.

Related

  1. Minimum-coordinate elimination on a simplex: polynomial first-step safety and coNP-complete correctness
    Arseny Kosachev
    arXivPreprintCC BY 4.0Full textOptimisation & controlarXiv
  2. On Control of Drawdown: Robust Invariance and Optimality
    Chung-Han Hsieh
    arXivPreprintarXiv licenceFull textOptimisation & controlarXiv
  3. Empirical Bayes prepivoting under group invariance: false discovery rate control and moderated t-tests
    Nikolaos Ignatiadis, Etienne Roquain
    arXivPreprintarXiv licenceFull textStatisticsarXiv
  4. A Complete Equational Theory for Quantum Circuits with Generalized Control
    William Schober, Scott Wesley
    arXivPreprintCC BY 4.0Full textAlgebra & number theoryarXiv
  5. Admissibility and Complete Classes for False Discovery Rate Control with E-values
    Liulei Sun, Ruodu Wang
    arXivPreprintarXiv licenceFull textStatisticsarXiv

Cite

BibTeXRIS
BibTeX
@misc{villanueva2026verifying,
  title = {{Verifying Control Invariance of H-Polytopes is coNP-Complete}},
  author = {Mario Eduardo Villanueva and Boris Houska},
  howpublished = {arXiv},
  year = {2026},
  month = oct,
  doi = {10.48550/arxiv.2610.36773},
  eprint = {2610.36773},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2610.36773},
  note = {CC BY 4.0},
}
RIS
TY  - UNPB
TI  - Verifying Control Invariance of H-Polytopes is coNP-Complete
AU  - Mario Eduardo Villanueva
AU  - Boris Houska
PY  - 2026
DA  - 2026/10/27
PB  - arXiv
DO  - 10.48550/arxiv.2610.36773
UR  - https://arxiv.org/abs/2610.36773
AB  - 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.
ER  -