Are there any known reversible pairing functions $f: \mathbb N \times \mathbb N \to \mathbb N$ that can be computed in constant time (FAC⁰)?
$\begingroup$
$\endgroup$
6
-
$\begingroup$ I have found the function by Pigeon described at mathworld.wolfram.com/PairingFunction.html Its recursive nature naively puts it out of constant time. $\endgroup$– Niall MurphyCommented Apr 7, 2010 at 18:35
-
2$\begingroup$ Could you define FAC^0? Do you mean that each bit of the result is AC^0? $\endgroup$– François G. DoraisCommented Apr 7, 2010 at 22:18
-
$\begingroup$ (I removed [set-theory] and added [complexity-theory].) $\endgroup$– François G. DoraisCommented Apr 7, 2010 at 23:14
-
$\begingroup$ (I TeXed OP's math notation, because OP's times symbol was mis-sized.) $\endgroup$– Theo Johnson-FreydCommented Apr 8, 2010 at 2:42
-
$\begingroup$ François, FAC⁰ is the set of functions computable by FO-uniform constant depth Boolean circuits (using AND, OR and NOT gates). So yes, each bit can be computed in AC⁰. (sorry didn't define this before hand) $\endgroup$– Niall MurphyCommented Apr 8, 2010 at 9:06
|
Show 1 more comment
2 Answers
$\begingroup$
$\endgroup$
6
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.
answered Apr 7, 2010 at 17:38
-
$\begingroup$ Unfortunately multiplication with two variables is known not to be in AC⁰ (though multiplication by a constant is in AC⁰). Is it the case that pairing functions must always be polynomial? If so then the only way it would be possible to compute such a function in constant time would be via some number theory tricks? $\endgroup$ Commented Apr 7, 2010 at 18:34
-
2$\begingroup$ Niall, pairing functions need not be polynomial. I expect, for example, that the binary-digit-interleaving function is not polynomial. $\endgroup$ Commented Apr 7, 2010 at 18:47
-
2$\begingroup$ I can't think of a reasonable definition of FAC^0 that interleaving bits does not satisfy. $\endgroup$ Commented Apr 7, 2010 at 22:40
-
$\begingroup$ After thinking a bit more its clear the interleaving pairing function is computed easily in FAC⁰. However, the problem is now to make it uniform. (i.e each circuit with $n$ input gates should compute the pairing function for all pairs of numbers whose concatenated binary encodings are length $n$) e.g 10d=1010b, 4d=100b gives input 1010100. How to tell where one number ends and the other begins? One idea is to encode one number backwards so the most sig. bits are at the ends of the string. Then interleave the bits from the ends and use the first $n$ bits of these as the answer. $\endgroup$ Commented Apr 8, 2010 at 9:20
-
$\begingroup$ @Niall: Why does the input have to be concatenated? You might as well have the input interleaved, no? It seems that your definition also has problems with the "1st bit of the second number" function. $\endgroup$ Commented Apr 8, 2010 at 14:38
$\begingroup$
$\endgroup$
Interleaving the binary encodings of the two numbers a and b seems to be the best solution:
For example the encoding of
a = 20d = 10100b
b = 5d = 101b
We interleave the bits starting with the least significant bits (we pad shorter numbers with 0's so they are the same length).
The resulting paired number is 0100110010b = 306d
This pairing function can be computed and reversed by a constant depth (depth 1?) circuit and so is in FAC0.
See:
- http://mathworld.wolfram.com/PairingFunction.html
- Pigeon, P. Contributions à la compression de données. Ph.D. thesis. Montreal, Université de Montréal, 2001. (page 115)