Computing a function without knowing the arguments

A forum for good logic/math puzzles.

Moderators: jestingrabbit, Moderators General, Prelates

>-)
Posts: 527
Joined: Tue Apr 24, 2012 1:10 am UTC

Computing a function without knowing the arguments

Postby >-) » Mon Dec 14, 2015 8:17 pm UTC

This puzzle based on some math/science blog I came across. Also it's apparently applicable to QM.

Suppose each of your two friends has n particular fixed boolean values.
You want to find the boolean result when those values are plugged into a boolean function f of 2n arguments (with the first friend's n values being the first n arguments and the second friend's being the last n).

This function is known to you and your friends. There are no restrictions beyond the requirement that only a single bit of information can be sent from each of your friends to you, and no other commuication can happen between anyone.
You are able to discuss strategy before the function and the particular boolean values are given.

How can this be accomplished?

Cauchy
Posts: 602
Joined: Wed Mar 28, 2007 1:43 pm UTC

Re: Computing a function without knowing the arguments

Postby Cauchy » Tue Dec 15, 2015 7:02 am UTC

This is not possible for n >= 2.

For n = 2, consider the function that looks at the two pairs of boolean values and treats them as integers between 0 and 3, inclusive; the function returns 0 when the sum of the two integers is congruent to 0 or 1 mod 4, and 1 when their sum is 2 or 3 mod 4.

Both friends' information-passing algorithm must be of the form "for each potential n-tuple of boolean values (a.k.a. for each potential integer) I receive, I pass either 0 or 1".

If the second friend receives the integer 1, he passes some value to you. Then, if the first friend receives a 0, he passes some value A to you, and if he receives a 1, he passes some value B to you. However, f(0,1) is not the same as f(1,1); since the second friend passes the same value to you in both cases, it must be the case that A and B are different.

Similarly, if the second friend receives a 0, he passes some value to you. The first friend passes A on 0, B on 1, and C on 2. Since f(2,0) is different from either of f(0,0) or f(1,0), C must be different from each of A and B.

So A, B, and C are all different. This can't happen if the first friend is only allowed to pass a single bit of information to you.

For n > 2, consider the function that throws away all but the first two bits of each friend's tuple and then behaves as above. It runs into the same problem.

More generally: for any two tuples x_1 and x_2 that the first friend has, if f(x_1, y) is different from f(x_2, y) for any tuple y that the second friend could receive, then the first friend can't pass the same bit of information to you for x_1 and x_2. It's easy to construct a function that differentiates each tuple that the first friend could receive, and so the first friend can't get away with passing less than n bits of information to you. Similarly for the second friend.
(∫|p|2)(∫|q|2) ≥ (∫|pq|)2
Thanks, skeptical scientist, for knowing symbols and giving them to me.

>-)
Posts: 527
Joined: Tue Apr 24, 2012 1:10 am UTC

Re: Computing a function without knowing the arguments

Postby >-) » Tue Dec 15, 2015 1:00 pm UTC

I see what you're saying, but I'm still quite sure there exists a solution. Here's a bit of a hint

Spoiler:
You'll need some sort of machine, which both friends pass information into, and both friends receive information from. Of course, it's important that the machine not be used to transmit between friends more than a single bit of information, if any at all.

HonoreDB
Posts: 161
Joined: Tue Feb 06, 2007 4:32 pm UTC
Contact:

Re: Computing a function without knowing the arguments

Postby HonoreDB » Tue Dec 15, 2015 4:28 pm UTC

Seems like your hint makes it trivial?

Spoiler:
Build a machine that takes input and computes the function. Each person inputs their own half of the input. The machine computes the function and outputs the result. No communication between sentient beings has occurred.


Which is clearly not what you had in mind, so maybe the problem needs some more explicit rules :)

Cauchy
Posts: 602
Joined: Wed Mar 28, 2007 1:43 pm UTC

Re: Computing a function without knowing the arguments

Postby Cauchy » Tue Dec 15, 2015 4:53 pm UTC

It sounds like you're stretching the definition of "communication between" very far; I would argue it's past the breaking point.

I assume the answer you're looking for is something along the lines of "you create a magic function that takes the 2n inputs, and then reports back to each friend a 0 or a 1. They pass this bit to you, and then you xor them for your answer. Because of the xor, each friend does not actually learn anything about the other friend's tuple." But this machine is still *communication* between the friends. For a given tuple that the first friend has, sometimes he'll be told by the machine to report a 0 to you and sometimes he'll be told to report a 1. This decision does not come from himself, and obviously the magic function isn't sentient, so the change comes about as a result of the second friend, and hence they are communicating.

Actually, thinking on it, for the first friend to gain *no* information about the second's tuple, it would need to be possible for any input from the second friend to cause either a 0 or a 1. So the magic function needs an external source of randomness (like collapsing a quantum state, where I guess the QM connection comes in). Somehow, this feels even worse; not only are they actually communicating, they're additionally not communicating further only because they're both taking orders from the same source, which is "not communicating" in some sneaky sense that doesn't feel like it respects the spirit of not communicating. This becomes much more clear if you replace the magic function and its randomness with a third friend flipping a coin.
(∫|p|2)(∫|q|2) ≥ (∫|pq|)2
Thanks, skeptical scientist, for knowing symbols and giving them to me.

>-)
Posts: 527
Joined: Tue Apr 24, 2012 1:10 am UTC

Re: Computing a function without knowing the arguments

Postby >-) » Tue Dec 15, 2015 5:26 pm UTC

Hmm, yeah I guess the puzzle was poorly designed, and I'm not sure how to state it in a nice way, but this is what I initially intended:

Have a machine which takes x, y in and returns r, s such that r xor s is x and y. Pick r and s randomly so the output is completely random to both friends.
The boolean function can be written as a polynomial, and each term XY, where X is in terms of values the first friend has and Y in terms of values the second has.
The polynomial is the sum of all these XY, but this can be written as the sum of the R's and the S's, which can be found using the machine.
Then one friend sends you the sum of the R's and the other sends you the sum of the S's, and you can xor them together.

This is based off of this paper (except they used only 2 parties and I added a third, because I enjoy symmetry)
http://arxiv.org/abs/quant-ph/0501159

I don't know much physics, so I can only guess that the reason the process in the paper had to be so elaborate, rather than having the machine just compute the value outright, as HonoreDB and Cauchy suggested, is that these quantum correlations can't be made so elaborate as to carry out arbitrary computations, but are only good enough for simple calculations. I'm just speculating here. Anyway, I did specify the problem badly, and I'm not sure if it can be worded in a way which makes more sense. I do think the idea of the one-bit distributed computing is interesting though.

User avatar
jestingrabbit
Factoids are just Datas that haven't grown up yet
Posts: 5967
Joined: Tue Nov 28, 2006 9:50 pm UTC
Location: Sydney

Re: Computing a function without knowing the arguments

Postby jestingrabbit » Fri Dec 18, 2015 3:10 am UTC

Whilst I'm not saying that I'm an expert in such things, I would like to suggest that the paper is not saying that a solution to this problem is possible. It is saying that if an apparent upper bound of quantum mechanics can be violated in the most extreme way, then there is a solution. Its a reductio ad absurdum, in the same way that Schroedinger's cat is a reductio ad absurdum.

I also thought I'd mention that a qubit is not a bit. I don't thing that's entirely relevant here, but its something worth knowing if you're going to be heading off in this direction.

I also really firmly believe that giving two people access to the same box is a communication, at least in the sense used in cryptographic problems and their like, which is where I would place this problem.
ameretrifle wrote:Magic space feudalism is therefore a viable idea.


Return to “Logic Puzzles”

Who is online

Users browsing this forum: No registered users and 8 guests