Regularity properties such as the incoherence condition, the restricted isometry property, compatibility, restricted eigenvalue and iq sensitivity of covariate matrices play a pivotal role in high-dimensional regression and compressed sensing. Yet, like computing the spark of a matrix, we first show that it is NP-hard to check the conditions involving all submatrices of a given size.