- #1
cam875
- 228
- 0
I was learning about boolean functions and the boolean satisfiability problem when I thought about what if we constructed a problem where you had two things: the domain and the range of a particular boolean function b. And the problem was that you had to solve for the boolean function which creates the appropriate mapping from the domain to the range.
So unlike the boolean satisfiability problem where you have to find appropriate values of either 1 or 0 to substitute into the function to make the function true you have the values but not the function. An example would be:
{0,0,0} -> 1
{0,1,0} -> 1
{0,1,1} -> 0
From this set of data you can conclude that b(0,00) = 1, b(0,1,0) = 1, and b(0,1,1) = 0
obviously this is a short example but the point would be to construct the function which creates this mapping. It seems that the only way to do so would be to perform an exhaustive search. As you can see this seems to be a one way type problem due to the fact that given a boolean function it is simple to compute all outputs for every possible input(2^n where n is the number of variables to the function) but take away the function and it seems to be become a computationally hard problem to solve for the function, hence the one wayness.
I am not sure though if it actually is one way and if this problem already exists.
I am working on this for my cs project so any help is greatly appreciated. Thanks in advance.
So unlike the boolean satisfiability problem where you have to find appropriate values of either 1 or 0 to substitute into the function to make the function true you have the values but not the function. An example would be:
{0,0,0} -> 1
{0,1,0} -> 1
{0,1,1} -> 0
From this set of data you can conclude that b(0,00) = 1, b(0,1,0) = 1, and b(0,1,1) = 0
obviously this is a short example but the point would be to construct the function which creates this mapping. It seems that the only way to do so would be to perform an exhaustive search. As you can see this seems to be a one way type problem due to the fact that given a boolean function it is simple to compute all outputs for every possible input(2^n where n is the number of variables to the function) but take away the function and it seems to be become a computationally hard problem to solve for the function, hence the one wayness.
I am not sure though if it actually is one way and if this problem already exists.
I am working on this for my cs project so any help is greatly appreciated. Thanks in advance.