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