How can you ask someone to prove his computational power over the phone ? Or rather, which type of math formula using common maths where the simplest case yields maximum computational complexity ?
Rules :
- There are no cases where the challenge being asked should simplify to the point it can be done by hand or on simple ᴄᴘᴜ like Z80.
- Callee is not aware of the type of challenge he will be prompted to so he/she isn’t able to precompute the result, thus he/she must not be able to look for a precomputed result online (like finding a nth trillion digit of ℯ).
- The result should consist of digits in order to be possibly dialed.
- As dialing or dictating long numbers manually is error prone, the challenge as well as the result should consist of numbers no longer than 9 digits and it should involve as fewest verbal steps as possible. No more than 5 steps.
- It should not be possible to guess the result trivially in a probabilistic manner : this excludes yes/no questions or cases where the result is between 0 and 9 or things like asking the color of a pixel.
- It should be platform agnostic : it should take 2 minutes on an high‑end Casio if the requirement is low or with using only ɢᴍᴘ/ᴍᴘꜰʀ on a high end computer if the requirement is high. As a result, this tends to exclude common hash functions.
- ʀᴀᴍ requirement is preferred over speed.
I tried to search on various things, but either dictating 1 billion digits long number is required or extracting 5 or 3 digits from the answer allow huge simplifications for computing the challenge compared to a naïve way : many times to the point doing it turns to be possible to compute it manually.
It sounds like you want something that is computationally irreducible:
https://en.wikipedia.org/wiki/Computational_irreducibility
That is, you want an algorithm that takes a certain number of computations to obtain a result that couldn't be obtained in a faster way. For example, the algorithm "add a to b n times" yields an answer that can be obtained in far fewer than $n$ computations for large $n$.
Israeli and Goldenfeld report that Wolfram's Cellular Automata "Rule 110" is irreducible in this way:
https://arxiv.org/abs/nlin/0309047
Thus, you could ask them to implement some number of cycles (depending on how many computations you want the to do) of "Rule 110" on a system with a given size and initial conditions and ask them to report the final state, or part of it, over the phone to verify that they can do that many cycles. (One downside is that you'd also need to do this many cycles to verify that their answer was correct. If you don't want to have to do the cycles yourself you'd need to ask them to do something like factoring large primes, where the results can be verified much more quickly than they can be obtained.)
EDIT: Here's how you could describe the problem over the phone: "Initialize your system in the following state, represented as n binary variables: [provide list of n ones and zeros]. Now, evolve the system forward m times and read out for me the final state [or part of the final state, if the final state is too long]. In each evolution, a site's value will be a function of the previous values of itself and of its left and right neighbors, defined cyclically. For example, cell 5's new state will depend on the states of cells 4, 5 and 6. Cell 1's new state will depend on cells n, 1 and 2. Those three cells can take on eight values. If the values are 111, 100, 001 or 000 (that is, if they're all the same or if a single noncentral cell is the only nonzero value) return 0, otherwise return 1.