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 (TDI) or not, is co-NP-complete. These 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.
Bibtex entry:
@techreport{egres-08-15,
AUTHOR | = | {Pap, J{\'u}lia}, |
TITLE | = | {Recognizing conic TDI systems is hard}, |
NOTE | = | {{\tt www.cs.elte.hu/egres}}, |
INSTITUTION | = | {Egerv{\'a}ry Research Group, Budapest}, |
YEAR | = | {2008}, |
NUMBER | = | {TR-2008-15} |