Are there any pairing functions computable in constant time (AC⁰) - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-22T20:17:31Z http://mathoverflow.net/feeds/question/20646 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/20646/are-there-any-pairing-functions-computable-in-constant-time-ac Are there any pairing functions computable in constant time (AC⁰) Niall Murphy 2010-04-07T17:24:02Z 2010-04-09T08:46:11Z <p>Are there any known reversible pairing functions <code>$f: \mathbb N \times \mathbb N \to \mathbb N$</code> that can be computed in constant time (FAC⁰)?</p> http://mathoverflow.net/questions/20646/are-there-any-pairing-functions-computable-in-constant-time-ac/20648#20648 Answer by Joel David Hamkins for Are there any pairing functions computable in constant time (AC⁰) Joel David Hamkins 2010-04-07T17:38:11Z 2010-04-07T17:57:22Z <p>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 <a href="http://books.google.com/books?id=2iJnkaFSojEC&amp;pg=PA443&amp;lpg=PA443&amp;dq=%22polynomial+pairing+function%22&amp;source=bl&amp;ots=2vNse7wfsf&amp;sig=SG_Zy32gr2-ySyjxNuL-ixBlijw&amp;hl=en&amp;ei=nMG8S7XBHoPe9ASnnfGBCA&amp;sa=X&amp;oi=book_result&amp;ct=result&amp;resnum=2&amp;ved=0CAsQ6AEwAQ#v=onepage&amp;q=%22polynomial%20pairing%20function%22&amp;f=false" rel="nofollow">here</a>.</p> <p>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.</p> <p>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. </p> <p>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.</p> http://mathoverflow.net/questions/20646/are-there-any-pairing-functions-computable-in-constant-time-ac/20755#20755 Answer by Niall Murphy for Are there any pairing functions computable in constant time (AC⁰) Niall Murphy 2010-04-08T16:28:04Z 2010-04-09T08:46:11Z <p>Interleaving the binary encodings of the two numbers a and b seems to be the best solution:</p> <p>For example the encoding of <br/> a = 20d = 10100b<br/> b = 5d = 101b<br/> We interleave the bits starting with the least significant bits (we pad shorter numbers with 0's so they are the same length).<br/> The resulting paired number is 0100110010b = 306d</p> <p>This pairing function can be computed and reversed by a constant depth (depth 1?) circuit and so is in FAC<sup>0</sup>.</p> <p>See:<br/> - <a href="http://mathworld.wolfram.com/PairingFunction.html" rel="nofollow">http://mathworld.wolfram.com/PairingFunction.html</a><br/> - Pigeon, P. Contributions à la compression de données. Ph.D. thesis. Montreal, Université de Montréal, 2001. (page 115) </p>