The procedure above can be implemented in polynomial time in the size of \(\mathbf {X}\) : Step 1 corresponds to checking whether an LP on polynomially many variables is feasible; step 2 has polynomial run-time by virtue of a result in [1]} (cf. [2]}); step 3 corresponds to checking feasibility of a system of linear Diophantine equations on polynomially many variables, which can be done in polynomial time by computing the Hermite or the Smith normal forms of the matrix of coefficients, see [3]}.
