In the paper The complexity of recognizing linear systems with certain integrality properties, Guoli Ding, Li Feng & Wenan Zang, Mathematical Programming 114, pages 321–334 (2008) the authors prove that testing integrality is coNP-complete.
Thomas Kalinowski
- 3k
- 2
- 19
- 27