Re: {0,1} Matrix Problem

Discussion in 'C++' started by Andrew Tomazos, May 2, 2009.

  1. 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, May 2, 2009
    #1
    1. Advertising

  2. On May 2, 4:11 am, Andrew Tomazos <> 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.
    Andrew Tomazos, May 2, 2009
    #2
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Junmou Zhang
    Replies:
    0
    Views:
    1,407
    Junmou Zhang
    Jul 10, 2003
  2. lvcargnini

    Matrix composed by two matrix

    lvcargnini, Jul 4, 2006, in forum: VHDL
    Replies:
    3
    Views:
    2,647
    Jonathan Bromley
    Jul 5, 2006
  3. Holgerson

    Matrix*Vector and Vector*Matrix

    Holgerson, Oct 25, 2007, in forum: C++
    Replies:
    3
    Views:
    398
    Holgerson
    Oct 26, 2007
  4. Terry Reedy
    Replies:
    0
    Views:
    542
    Terry Reedy
    Apr 2, 2009
  5. Robert Kern
    Replies:
    0
    Views:
    581
    Robert Kern
    Apr 2, 2009
Loading...

Share This Page