Timeline for Are there any pairing functions computable in constant time (AC⁰)
Current License: CC BY-SA 2.5
9 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Apr 8, 2010 at 16:23 | comment | added | Niall Murphy | @Fraçois: Yes you are right. I was worried that assuming the numbers are interleaved initially is too strong for an input encoding but I think it is fine. The point is that the two unique numbers can decoded in constant time. | |
| Apr 8, 2010 at 14:38 | comment | added | François G. Dorais | @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. | |
| Apr 8, 2010 at 9:20 | comment | added | Niall Murphy | 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. | |
| Apr 7, 2010 at 22:40 | comment | added | François G. Dorais | I can't think of a reasonable definition of FAC^0 that interleaving bits does not satisfy. | |
| Apr 7, 2010 at 18:47 | comment | added | Joel David Hamkins | Niall, pairing functions need not be polynomial. I expect, for example, that the binary-digit-interleaving function is not polynomial. | |
| Apr 7, 2010 at 18:34 | comment | added | Niall Murphy | 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? | |
| Apr 7, 2010 at 17:57 | history | edited | Joel David Hamkins | CC BY-SA 2.5 |
added 340 characters in body
|
| Apr 7, 2010 at 17:47 | history | edited | Joel David Hamkins | CC BY-SA 2.5 |
added 266 characters in body; added 2 characters in body
|
| Apr 7, 2010 at 17:38 | history | answered | Joel David Hamkins | CC BY-SA 2.5 |