HEXAGONbeta

The inverse quiver problem is NP-complete

Primarily human-written textHuman understanding: all partsmath.RT — Representation Theory

Contributed by Paul, Marin, Pierre Coutant--Denord ↗

Version 1 / Oct 07, 2026 / CC BY 4.0

Abstract

We prove that the inverse quiver problem is NP-complete. We also present a new proof that the quiver problem is NP-complete. We present a way to translate arithmetical/algebraic geometry problems in terms of (inverse) quiver problem.

Provenance statement

This work was produced during an internship at IHES under the supervision of Victor Kac. My goal was to simplify the proof in the paper “The quiver problem is NP-complete.” In doing so, I discovered a fun way to reformulate classical problems in terms of quivers. DeepL was used to translate from French to English.

References

  1. Bellini, Emanuele; Makarim, Rusydi H.; Sanna, Carlo; Verbel, Javier. An Estimator for the Hardness of the MQ Problem. pp. 323-347. 2022DOI
  2. Victor Kac; Bangzheng Li. The quiver problem is NP-complete. Journal of Algebra, vol. 697, pp. 145-156. 2026DOI
  3. Kac, Victor G. Infinite root systems, representations of graphs and invariant theory. Inventiones mathematicae, vol. 56, no. 1, pp. 57–92. 1980
  4. Victor G. Kac. On complexity of representations of quivers. Comptes Rendus. Mathématique, vol. 357, no. 11-12, pp. 841–845. 2019DOI
  5. Andrew Wiles. Modular Elliptic Curves and Fermat's Last Theorem. Annals of Mathematics, vol. 141, no. 3, pp. 443–551. 1995link

Version history

  1. v1Submitted by Paul, Marin, Pierre Coutant--DenordRevised after moderator-requested changesCurrentOct 07, 2026