Velocity Reviews > C++ > Re: {0,1} Matrix Problem

# Re: {0,1} Matrix Problem

Andrew Tomazos
Guest
Posts: n/a

 05-02-2009
So lets restate:

- Let U be the set of all matrices over {0, 1} that have no all-zero
columns.

- Given a member of U, is it possible to remove k rows and stay inside
U?

- This is an NP-complete problem.

- Providing a polynomial time solution would prove N=NP.

- Proving that there is no polynomial time solution would prove N !=
NP.

When we talk about polynomial time in this case, are we talking
relative to the width of the matrix, the height of the matrix or the
value k?

Clearly the naive recursive solution (I have written up a C++ version
below) of trying to remove each row and then solving each for (k-1) is
bounded above within constant factors of:

(height ^ (k+1) ) * width

Is this correct? If k is considered constant than this would be a
polynomial time solution. Clearly that cannot be the case?
-Andrew.

#include <vector>
#include "stdio.h"

typedef std::vector < std::vector < bool > > BoolMatrix;

int Height(BoolMatrix m) { return m.size(); }

int Width(BoolMatrix m) { return m[0].size(); }

// U(m): Is the BoolMatrix a member of the set U?
bool U(BoolMatrix m)
{
for (int col = 0; col < Width(m); col++)
{
bool allzero = true;

for (int row = 0; row < Height(m); row++)
if (m[row][col])
allzero = false;

if (allzero)
return false;
}

return true;
}

// RemoveRow(m, i): Remove the ith row from a BoolMatrix
void RemoveRow(BoolMatrix& m, int row)
{
m.erase(m.begin() + row);
}

// solve(m,k): Can you remove k rows from a BoolMatrix and stay in U?
bool solve(BoolMatrix m, int k)
{
// if the BoolMatrix is not in U to begin with, than NO
if (!U(m))
return false;

// if k is 0 and the BoolMatrix is in U, than trivially YES
if (k == 0)
return true;

// For each row in the BoolMatrix...
for (int row = 0; row < Height(m); row++)
{
// Try removing this row
BoolMatrix reduced = m;
RemoveRow(reduced, row);

// Can we remove k-1 rows from the reduced BoolMatrix
// and stay in U?
if (solve(reduced, k-1))
{
// If we can than the answer is YES
return true;
}

}

// Could not find any solution, so the answer is NO
return false;
}

Andrew Tomazos
Guest
Posts: n/a

 05-02-2009
On May 2, 4:11*am, Andrew Tomazos <(E-Mail Removed)> wrote:
> - Providing a polynomial time solution would prove N=NP.
>
> - Proving that there is no polynomial time solution would prove N!=NP.

Ahh... make that "P=NP" and "P!=NP" of course.
-Andrew.