We are given an $n\times (n+k)$ matrix $A,$ with entries in $\mathrm{GF}(2),$ of the form $A=(I_n|B)$ where $I_n$ is a $n\times n$ identity matrix where the matrix $B$ has no "zero" rows or columns.

The problem is to partition the columns of $A$ into at most $m$ subsets each of size at most $b$ such that the number of "critical subset's" is minimized, where a critical subset is a subset of the set of columns such that if we remove it from $A$ the reduced matrix has rank less than $n.$

The problem seems to be NP-Complete to me but I am not able to understand from which problem we should try to reduce.

The elaborate problem definition/relevant discussion can be found at:

http://math.stackexchange.com/questions/57412/optimization-problem-for-a-parity-check-code.

I am defining it here in some abstract way. Also, I wanted to post it under the NP-Complete tag.

We are given an $n\times (n+k)$ matrix $A,$ with entries in $\mathrm{GF}(2),$ of the form $A=(I_n|B)$ where $I_n$ is a $n\times n$ identity matrix where the matrix $B$ has no "zero" rows or columns.

The problem is to partition the columns of $A$ into at most $m$ subsets each of size at most $b$ such that the number of "critical subset's" is minimized, where a critical subset is a subset of the set of columns such that if we remove it from $A$ the reduced matrix has rank less than $n.$

The problem seems to be NP-Complete to me but I am not able to understand from which problem we should try to reduce.

The elaborate problem definition/relevant discussion can be found at:

https://math.stackexchange.com/questions/57412/optimization-problem-for-a-parity-check-code.

I am defining it here in some abstract way. Also, I wanted to post it under the NP-Complete tag.

We are given an nx(n+k) matrix A, with entries in GF(2), of the form A=(In|B) where In is a nxn identity matrix where the matrix B has no "zero" rows or columns.

The problem is to partition the columns of A into atmost m subsets each of size atmost b such that the number of "critical subset"s is minimized, where a critical subset is a subset of the set of columns such that if we remove it from A the reduced matrix has rank less than n.

The problem seems to be NP-Complete to me but not able to understand from which problem we should try to reduce.

The elaborate problem definition/relevant discussion can be found at  http://math.stackexchange.com/questions/57412/optimization-problem-for-a-parity-check-code. I am defining here in some abstract way. Also, I wanted to post it under NP-Complete tag.

We are given an $n\times (n+k)$ matrix $A,$ with entries in $\mathrm{GF}(2),$ of the form $A=(I_n|B)$ where $I_n$ is a $n\times n$ identity matrix where the matrix $B$ has no "zero" rows or columns.

The problem is to partition the columns of $A$ into at most $m$ subsets each of size at most $b$ such that the number of "critical subset's" is minimized, where a critical subset is a subset of the set of columns such that if we remove it from $A$ the reduced matrix has rank less than $n.$

The problem seems to be NP-Complete to me but I am not able to understand from which problem we should try to reduce.

The elaborate problem definition/relevant discussion can be found at:

http://math.stackexchange.com/questions/57412/optimization-problem-for-a-parity-check-code. 

I am defining it here in some abstract way. Also, I wanted to post it under the NP-Complete tag.

We are given an nx(n+k) matrix A, with entries in GF(2), of the form A=(In|B) where In is a nxn identity matrix where the matrix B has no non-zero rows or columns.

The problem is to partition the columns of A into atmost m subsets each of size atmost b such that the number of "critical subset"s is minimized, where a critical subset is a subset of the set of columns such that if we remove it from A the reduced matrix has rank less than n.

The problem seems to be NP-Complete to me but not able to understand from which problem we should try to reduce.

The elaborate problem definition/relevant discussion can be found at http://math.stackexchange.com/questions/57412/optimization-problem-for-a-parity-check-code. I am defining here in some abstract way. Also, I wanted to post it under NP-Complete tag.

We are given an nx(n+k) matrix A, with entries in GF(2), of the form A=(In|B) where In is a nxn identity matrix where the matrix B has no "zero" rows or columns.

The problem is to partition the columns of A into atmost m subsets each of size atmost b such that the number of "critical subset"s is minimized, where a critical subset is a subset of the set of columns such that if we remove it from A the reduced matrix has rank less than n.

The problem seems to be NP-Complete to me but not able to understand from which problem we should try to reduce.

The elaborate problem definition/relevant discussion can be found at http://math.stackexchange.com/questions/57412/optimization-problem-for-a-parity-check-code. I am defining here in some abstract way. Also, I wanted to post it under NP-Complete tag.