Hacker News Reader

Comment by throwaway080383 | Hacker News Reader

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?"

View on HN

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

If f has small K complexity, then f^-1 has small K complexity.

Is there a formal theorem making this precise?

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.

> 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.

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.

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.

Reply on news.ycombinator.com