Skip to main content
MathOverflow

Return to Answer

rephrasing part of Joel David Hamkins answer and giving an example
Source Link
Niall Murphy
Niall Murphy
  • 339
  • 2
  • 11

Bit interleavingInterleaving 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 two original numbersresulting paired number is 0100110010b = 306d

This pairing function can be easily decoded incomputed and reversed by a constant timedepth (depth 1?) circuit and so is in FAC0.

(see http://mathworld.wolfram.com/PairingFunction.html, and Pigeon, P. Contributions à la compression de données. Ph.D. thesis. Montreal, Université de Montréal, 2001. page 115) See:

Bit interleaving seems to be the best solution. The two original numbers can be easily decoded in constant time.

(see http://mathworld.wolfram.com/PairingFunction.html, and Pigeon, P. Contributions à la compression de données. Ph.D. thesis. Montreal, Université de Montréal, 2001. page 115)

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:

Source Link
Niall Murphy
Niall Murphy
  • 339
  • 2
  • 11

Bit interleaving seems to be the best solution. The two original numbers can be easily decoded in constant time.

(see http://mathworld.wolfram.com/PairingFunction.html, and Pigeon, P. Contributions à la compression de données. Ph.D. thesis. Montreal, Université de Montréal, 2001. page 115)