|
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:
| AUTHOR | = | {Pap, J{\'u}lia}, |
| TITLE | = | {Recognizing conic TDI systems is hard}, |
| NOTE | = | {{\tt egres.elte.hu}}, |
| INSTITUTION | = | {Egerv{\'a}ry Research Group, Budapest}, |
| YEAR | = | {2008}, |
| NUMBER | = | {TR-2008-15} |