Results 1 to 3 of 3

Math Help - NP or NP-hard?

  1. #1
    Newbie
    Joined
    Sep 2009
    Posts
    2

    NP or NP-hard?

    hi all

    i'm in the middle of writing my masters dissertation and i'm not sure whether the problem i'm trying to solve is NP-hard or merely NP (i should probably clarify that its not a masters in maths, its in cybernetics, so apologies if i suck too hard at the maths)

    anyway, the problem i'm attempting to solve is the k-bit multiplexer problem and it goes like this
    you have a sting of bits and some of the bits address the remainder of the bits. for example, in the 6-bit multiplexer(MUX), the first 2 bits address the second 4 bits

    101010

    here the first 2 bits give us the binary value for 2. the rest of the bit string is indexed from 0 from right to left, thus the value at index 2 is 0 and this bit string will output 0- the value at the indexed position:

    index__________3 2 1 0
    bit string___1 0 1 0 1 0

    clearly the only important values in that bit string are the address bits and the indexed value- we can ignore the other values.
    the idea is to write a program which will sub out all the unimportant values with a hash (#) to represent that we don't care what value that bit has. it also has to successfully predict the output. thus i am looking for a rules which are maximally general and look something like this:
    10#0##:0 (where the ":0" means predicted output is 0)

    i'm also looking for the maximally general incorrect rules, such as 10#0##:1

    those are just 2 rules for the 6bit MUX, of the 128 maximally general rules over all.

    now the k-bit MUX works in much the same way as this 6-bit example, except that it should be able to solve for many (any) lengths of bits.
    the calculations for the number of solutions are shown in the following table (size of search space)

    Multiplexer size_____ Number of address bits____Number of data bits__Size of search space
    ____________3___________________1_________________ ___2_____________________16
    ____________6___________________2_________________ ___4____________________128
    ___________11___________________3_________________ ___8___________________4096
    ___________20___________________4_________________ __16________________2097152
    ___________37___________________5_________________ __32__________2.74878 x10^11
    ___________70___________________6_________________ __64__________2.36118 x10^21
    __________135___________________7_________________ _128__________8.71123 x10^40
    __________264___________________8_________________ _256__________5.92855 x10^79
    __________521___________________9_________________ _512___________1.373 x10^157
    _________1034___________________10________________ 1024__________3.6817 x10^311
    _________2059___________________11________________ 2048__________1.3237 x10^620
    _________4108___________________12________________ 4096_________8.5556 x10^1236


    so my question is this- is this question NP or NP-hard?

    hopefully i explained it well enough but if not then let me know

    cheers
    dan
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Grand Panjandrum
    Joined
    Nov 2005
    From
    someplace
    Posts
    14,972
    Thanks
    4
    Quote Originally Posted by danyilmaz View Post
    hi all

    i'm in the middle of writing my masters dissertation and i'm not sure whether the problem i'm trying to solve is NP-hard or merely NP (i should probably clarify that its not a masters in maths, its in cybernetics, so apologies if i suck too hard at the maths)

    anyway, the problem i'm attempting to solve is the k-bit multiplexer problem and it goes like this
    you have a sting of bits and some of the bits address the remainder of the bits. for example, in the 6-bit multiplexer(MUX), the first 2 bits address the second 4 bits

    101010

    here the first 2 bits give us the binary value for 2. the rest of the bit string is indexed from 0 from right to left, thus the value at index 2 is 0 and this bit string will output 0- the value at the indexed position:

    index__________3 2 1 0
    bit string___1 0 1 0 1 0

    clearly the only important values in that bit string are the address bits and the indexed value- we can ignore the other values.
    the idea is to write a program which will sub out all the unimportant values with a hash (#) to represent that we don't care what value that bit has. it also has to successfully predict the output. thus i am looking for a rules which are maximally general and look something like this:
    10#0##:0 (where the ":0" means predicted output is 0)

    i'm also looking for the maximally general incorrect rules, such as 10#0##:1

    those are just 2 rules for the 6bit MUX, of the 128 maximally general rules over all.

    now the k-bit MUX works in much the same way as this 6-bit example, except that it should be able to solve for many (any) lengths of bits.
    the calculations for the number of solutions are shown in the following table (size of search space)

    Multiplexer size_____ Number of address bits____Number of data bits__Size of search space
    ____________3___________________1_________________ ___2_____________________16
    ____________6___________________2_________________ ___4____________________128
    ___________11___________________3_________________ ___8___________________4096
    ___________20___________________4_________________ __16________________2097152
    ___________37___________________5_________________ __32__________2.74878 x10^11
    ___________70___________________6_________________ __64__________2.36118 x10^21
    __________135___________________7_________________ _128__________8.71123 x10^40
    __________264___________________8_________________ _256__________5.92855 x10^79
    __________521___________________9_________________ _512___________1.373 x10^157
    _________1034___________________10________________ 1024__________3.6817 x10^311
    _________2059___________________11________________ 2048__________1.3237 x10^620
    _________4108___________________12________________ 4096_________8.5556 x10^1236


    so my question is this- is this question NP or NP-hard?

    hopefully i explained it well enough but if not then let me know

    cheers
    dan
    Sorry, but what are you searching for and why?

    CB
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Sep 2009
    Posts
    2
    i'm looking at abstraction in machine learning- abstraction being the way we humans can learn to play tic tac toe and then apply the knowledge from that to, say connect-4, or tic tac toe on a larger grid for example.

    i'm trying writing a program which looks at several smaller MUX problems (6-bit, 11-bit, 20-bit etc etc) and then tries to find the abstract rules that govern all of them (find the address bits, output the number in the indexed bit)

    i hope that makes it clearer
    cheers
    dan
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Hard one.
    Posted in the Calculus Forum
    Replies: 7
    Last Post: April 8th 2010, 01:36 PM
  2. ...A hard IVP?
    Posted in the Differential Equations Forum
    Replies: 2
    Last Post: December 11th 2009, 08:22 AM
  3. Help, it's hard! :-S
    Posted in the Advanced Algebra Forum
    Replies: 1
    Last Post: December 8th 2009, 02:45 PM
  4. g of hard
    Posted in the Pre-Calculus Forum
    Replies: 1
    Last Post: September 24th 2009, 04:09 AM
  5. Log Qn (Not too hard!!)
    Posted in the Calculus Forum
    Replies: 3
    Last Post: May 16th 2008, 08:01 AM

Search Tags


/mathhelpforum @mathhelpforum