Recognizing conic TDI systems is hard
2011
In this note we prove that the problem of deciding whether or not a set of integer vectors forms a Hilbert basis is co-NP-complete. Equivalently, deciding whether a conic linear system is totally dual integral or not, is co-NP-complete. These statements are true even if the vectors in the set or respectively the coefficient vectors of the inequalities are 0–1 vectors having at most three ones.
Keywords:
- Correction
- Source
- Cite
- Save
- Machine Reading By IdeaReader
8
References
14
Citations
NaN
KQI