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. Advertisements

  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. Advertisements

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,525
    Junmou Zhang
    Jul 10, 2003
  2. Richard Fagen

    Web Matrix problem, can't add table rows

    Richard Fagen, Aug 28, 2003, in forum: ASP .Net
    Replies:
    0
    Views:
    575
    Richard Fagen
    Aug 28, 2003
  3. Eugene
    Replies:
    0
    Views:
    419
    Eugene
    Mar 2, 2004
  4. Kim Bracknell

    Access Problem using Web Matrix

    Kim Bracknell, May 20, 2004, in forum: ASP .Net
    Replies:
    0
    Views:
    363
    Kim Bracknell
    May 20, 2004
  5. Replies:
    3
    Views:
    498
    =?Utf-8?B?Q29saW5fTW9ycmlz?=
    Aug 15, 2005
  6. Bob
    Replies:
    1
    Views:
    1,925
  7. lvcargnini

    Matrix composed by two matrix

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

    Matrix*Vector and Vector*Matrix

    Holgerson, Oct 25, 2007, in forum: C++
    Replies:
    3
    Views:
    608
    Holgerson
    Oct 26, 2007
Loading...