How many reversible integer operations do you know?

Re:How many reversible integer operations do you know? by ecesena on Sunday January 14, 2018 @01:27PM (#16145461)

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

[ Parent | on HN ]

Re:How many reversible integer operations do you know? by ogdan on Sunday January 14, 2018 @02:52PM (#16145969)

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

[ Parent | on HN ]

Re:How many reversible integer operations do you know? by nwjtkjn on Sunday January 14, 2018 @06:49PM (#16147310)

Is there a formal theorem making this precise?

[ Parent | on HN ]

Re:How many reversible integer operations do you know? by gizmo686 on Sunday January 14, 2018 @07:19PM (#16147465)

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.

[ Parent | on HN ]