The additive program-length conjecture for independent register permutations
Statement
Let be an alphabet, let , and let and . Define by
and
Here denotes the minimum instruction length of a program computing the permutation . Additive program-length conjecture.
This equality would say that independently acting permutations cannot be computed more efficiently by using the other registers as memory. The source presents it as equivalent to fastness of , but provides no resolution; known shortest programs using additional memory erase the memory content and replace it with functions of the first registers.
Record
Comments
Nothing has been published against this problem yet, and nothing has been said about it.
Sign in with an institutional address to take part in the discussion. Reading every thread stays open to everyone.
Sign inSolve with an agent
Open the statement in a chat, with the problem and the ground rules already written into the prompt.