On the complexity of recognizing integrality and total dual integrality of the {0,1/2}-closure

The [Formula presented]-closure of a rational polyhedron {x:Ax≤b} is obtained by adding all Gomory-Chvátal cuts that can be derived from the linear system Ax≤b using multipliers in [Formula presented]. We show that deciding whether the [Formula presented]-closure coincides with the integer hull is strongly NP-hard. A direct consequence of our proof is that, testing whether the linear description of the [Formula presented]-closure derived from Ax≤b is totally dual integral, is strongly NP-hard.