4 ms·

As others have pointed out, there are (2^32)! such operations on 32-bit ints. However, I think it can be shown that the Kolmogorov complexity of most of these h

As others have pointed out, there are (2^32)! such operations on 32-bit ints. However, I think it can be shown that the Kolmogorov complexity of most of these has to be O(lg((2^32)!)) which I think is rougly 32*2^32. In other words, you'd need about 16GB just to store the program to compute the permutation! Of course, that is not the case for the operations shown here. So maybe implicitly the real question is, "How many reversible integer operations do you know with small Kolmogorov complexity?" Or in more practical terms, "How many reversible integer operations do you know which don't require too many lines of code?"

wilun 9y ago
> In other words, you'd need about 16GB just to store the program to compute the permutation! Another way to reach this number is simply to consider that most reversible operations are going to be implementable by non-compressible LUTs, and such a LUT for 32-bits number will be 2^32 * 4 Bytes == 16GB.
- Retric 9y ago
  You can cut this in half because the inputs always map to different outputs and nothing repeats. So, after specifying the first mapping 0 > k, 1 can map to 2^32 -1 possible numbers, 2 can map to 2^32 - 2 numbers etc, and you can skip mapping the last number as only one possibility is left. LUT's would be vastly faster though.
ecesena 9y ago
I suspect he’s also implicitly assuming “the inverse is easy to compute”, so both the operation and its inverse have small K complexity.
- ogdan 9y ago
  If f has small K complexity, then f^-1 has small K complexity.
  - nwjtkjn 9y ago
    Is there a formal theorem making this precise?
    - gizmo686 9y ago
      I'm not familiar with the formal definition of Kolmogorov complexity, nor its related theorems, but informally, it appears to be about the length of the specifying program, not the time it takes to run. Given that we have a finite domain, and 1:1 functions, we should be able to specify f^-1 with some constant overhead and embedding f. Something along the lines of: //embed the definition of f. f^-1(x) = for a in Domain: if f(a) = x return a Formalizing this would involve specifying what description language you are using and how you encode functions.
zxcmx 9y ago
An easy way to access a large number of different permutations is to use a cipher and select a particular permutation with the key. In this sense the AES provides a much larger number of reversible operations than all those listed :) For 32 bit permutations my go-to is skipfish. It's not a great cipher but it produces permutations (for e.g. producing a random permutation of all IPv4 addresses) perfectly well.

wilun 9y ago

> In other words, you'd need about 16GB just to store the program to compute the permutation! Another way to reach this number is simply to consider that most reversible operations are going to be implementable by non-compressible LUTs, and such a LUT for 32-bits number will be 2^32 * 4 Bytes == 16GB.

Retric 9y ago
You can cut this in half because the inputs always map to different outputs and nothing repeats. So, after specifying the first mapping 0 > k, 1 can map to 2^32 -1 possible numbers, 2 can map to 2^32 - 2 numbers etc, and you can skip mapping the last number as only one possibility is left. LUT's would be vastly faster though.

ecesena 9y ago

I suspect he’s also implicitly assuming “the inverse is easy to compute”, so both the operation and its inverse have small K complexity.

ogdan 9y ago
If f has small K complexity, then f^-1 has small K complexity.
- nwjtkjn 9y ago
  Is there a formal theorem making this precise?
  - gizmo686 9y ago
    I'm not familiar with the formal definition of Kolmogorov complexity, nor its related theorems, but informally, it appears to be about the length of the specifying program, not the time it takes to run. Given that we have a finite domain, and 1:1 functions, we should be able to specify f^-1 with some constant overhead and embedding f. Something along the lines of: //embed the definition of f. f^-1(x) = for a in Domain: if f(a) = x return a Formalizing this would involve specifying what description language you are using and how you encode functions.

zxcmx 9y ago

An easy way to access a large number of different permutations is to use a cipher and select a particular permutation with the key. In this sense the AES provides a much larger number of reversible operations than all those listed :) For 32 bit permutations my go-to is skipfish. It's not a great cipher but it produces permutations (for e.g. producing a random permutation of all IPv4 addresses) perfectly well.