[This paper][1] shows that testing integrality is coNP-complete.


  [1]: http://www.springerlink.com/content/b88j0x7h3t210704/