@Mohsen Ah, I think I now understand where I misread your question. $A$ is a priori known to satisfy $\Gamma$? I was thinking it was unknown a priori! Sorry if I wasted your time... Anyway, Good luck!

@Mohsen Well, if $A$ is not even remotely random, my informal argument doesn't work. Sorry, but I can't know assumptions on $A$ because you didn't tell me. The question you wrote makes it sound like $A$ is taken randomly... Besides, you didn't tell whatever constrains on A you have in mind when I said you might want to impose restrictions on something. So, I guess I have to give up now because I don't know exactly what problem you want to solve...

So you should know if $d\geq\frac{t-1}{2}$. Now you didn't specify how $M$ is chosen. But, for example, assume that you may end up with $M$ with all subsets of size $c\cdot n$ for some constant $c$. In other words, your algorithm should determine if $d\geq c'\cdot n$ for some constant $c'$. Because the minimum distance of a random linear code satisfies the Gilbert-Varshamov bound with high probability, basically your algorithm should determine if $d\geq c''\cdot d$ for some constant $c''$, which seems unlikely to be in polynomial time.

@Mohsen A parity-check matrix $H$ doesn't have to be systematic. Take $M_x\in M$. Let $\boldsymbol{e}=(e_0,\dots,e_{n-1})$ be the $n$-dimensional vector such that $e_i=1$ if $i\in M_x$ and otherwise zero. A linear code defined by $H$ can correct error $\boldsymbol{e}$ if and only if (1) $H'$ that corresponds to columns specified by $M_x$ is full rank and (2) $H'$ with any other set of $\vert M_x\vert$ columns (which are not in $H'$) is also full rank. So, if $M$ contains all subsets of size $t$, the linear code should be of minimum distance at least $\frac{t-1}{2}$.

@Mohsen The randomized approach doesn't work that well. It's not in random polynomial time. See the edit of the answer.

@Mohsen Anyway, I revised this long comment to make it an answer. I hope this answers your question.

@Mohsen About $A'$ might be $TA$: But that doesn't change the situation, does it? Your definition of $\Gamma$ seems to say that $A'$ should be rows of $A$.

@Mohsen Oh, I forgot to put "do not" before "correspond." This is what you meant, I think?

@Mohsen Oh, I missed your comments before posting the "answer" that is actually a long comment. But I guess I made it clear exactly what you mean. I hope it's correct.

Is there some sort of assumption on $\boldsymbol{x}$? If I understand correctly, since $A$ is a fat matrix, you can't generally solve the linear equation. I'm guessing you're assuming that $\boldsymbol{x}$ is sparse (i.e., it has at most $s$ nonzero elements for some fixed small integer $s$). If this is the case, what you asked sounds the same as or closely related to MDS codes or the separating distance of $A$.