Timeline for Are there any pairing functions computable in constant time (AC⁰)
Current License: CC BY-SA 2.5
12 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Apr 9, 2010 at 18:02 | vote | accept | Niall Murphy | ||
| Apr 8, 2010 at 16:28 | answer | added | Niall Murphy | timeline score: 5 | |
| Apr 8, 2010 at 15:04 | comment | added | François G. Dorais | The uniformity requirements and the dual-input representation are the main issues. I can think of one reasonable choice for what FAC^0 should be, but your remarks below suggest that my choice is not the correct one. I would assume that however your dual-input is represented the "identity map" ought to be a pairing function. | |
| Apr 8, 2010 at 9:06 | comment | added | Niall Murphy | 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) | |
| Apr 8, 2010 at 2:42 | comment | added | Theo Johnson-Freyd | (I TeXed OP's math notation, because OP's times symbol was mis-sized.) | |
| Apr 8, 2010 at 2:41 | history | edited | Theo Johnson-Freyd | CC BY-SA 2.5 |
fixed some TeX
|
| Apr 7, 2010 at 23:14 | comment | added | François G. Dorais | (I removed [set-theory] and added [complexity-theory].) | |
| Apr 7, 2010 at 23:14 | history | edited | François G. Dorais |
edited tags
|
|
| Apr 7, 2010 at 22:18 | comment | added | François G. Dorais | Could you define FAC^0? Do you mean that each bit of the result is AC^0? | |
| Apr 7, 2010 at 18:35 | comment | added | Niall Murphy | I have found the function by Pigeon described at mathworld.wolfram.com/PairingFunction.html Its recursive nature naively puts it out of constant time. | |
| Apr 7, 2010 at 17:38 | answer | added | Joel David Hamkins | timeline score: 5 | |
| Apr 7, 2010 at 17:24 | history | asked | Niall Murphy | CC BY-SA 2.5 |