Are there any known reversible pairing functions $f: \mathbb N \times \mathbb N \to \mathbb N$ that can be computed in constant time (FAC⁰)?
Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)
|
1
|
|
|||||||||||||||||
|
|
3
|
The pairing function f(a,b) = (a + b)(a + b + 1)/2 + a is the one that arises by drawing diagonals on the natural number lattice, and marching down them from upper left to lower right. See the picture here. To compute f(a,b), one needs to perform some additions and a multiplication, which seems to be quadratic time in the length of a and b, that is, in log(a)+log(b), which would seem to be constant time in max(a,b), but I'm not sure if this would be what you meant. In that book, it is noted that Polya has proved that any surjective polynomial pairing function is equal to this function or to its dual form f(b,a). (And someone gave a talk here at CUNY a few weeks ago on precisely this fact.) So if this function is not acceptable to you, then you will find no polynomial surjective function. But here is another function, which seems to be a little faster to compute. Suppose that a and b are given to me in their binary representation. Now, I just interleave their binary digits, using 0's if the digits of one of them runs out. This is surely a pairing function, and I can compute it linear time of the lengths of the input. |
|||||||||||||||||||
|
You can accept an answer to one of your own questions by clicking the check mark next to it. This awards 15 reputation points to the person who answered and 2 reputation points to you.
|
2
|
Interleaving the binary encodings of the two numbers a and b seems to be the best solution: For example the encoding of This pairing function can be computed and reversed by a constant depth (depth 1?) circuit and so is in FAC0. See: |
|||
|
|
