NP or NP-hard?

• Sep 28th 2009, 04:17 AM
danyilmaz
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
• Sep 28th 2009, 05:53 AM
CaptainBlack
Quote:

Originally Posted by danyilmaz
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
• Sep 28th 2009, 06:55 AM
danyilmaz
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