Function with no fast path and with fast proof When a function is iterated and each time a previous result is used as input to the next iteration (feedback), so that there is a limited benefit from parallel computing, is there such function that:


requires polynomial time to get the result of N iterations
has an Nth result that can be verified in constant time to be the Nth result for a given start value


Assuming that Alice iterates the function:

Problem with Makwa: At first Bob must use and throw away p and q.

Problem with LCS35: At first Bob must construct the puzzle.

But I need a function so that Alice can choose an arbitrary number or data to begin iterating with, not something prepared by Bob. Only when Alice has done N iterations Bob will join and verify.
The following paragraph applies even if the honest prover does not use iteration.

Strictly speaking, only a constant-size part of the input can be read from in

constant time, so one could always find a suitable result in constant time.

For a deterministic verifier that makes at most k probes to an alleged result

consisting of M w-bit words, one can find a suitable result with ​ 2$\hspace{.02 in}$w$\hspace{.02 in}\cdot$k ​ parallel

simulations of the verifier, each of which uses only ​ $(\hspace{.02 in}2\hspace{-0.05 in}\cdot \hspace{-0.04 in}k)\hspace{-0.04 in}+\hspace{.02 in}$O(1) ​ words of overhead.

If instead the verifier is probabilistic, then either ​ $\binom{M}{\hspace{.02 in}k\cdot \hspace{.02 in}(1+\hspace{.03 in}\Omega(1))\hspace{-0.03 in}}$$\cdot$2$\hspace{.02 in}$w$\hspace{.02 in}\cdot$k$\cdot$(1+$\hspace{.03 in}$Ω(1)) ​ parallel

simulations will be enough, or the adversary can very-efficiently go from an actual result

to one that makes the verifier's acceptance probability be between Ω(1) and 1-$\hspace{.02 in}$Ω(1).

However, it may well be possible to achieve what you're asking about with a probabilistic

word RAM verifier, by simply accepting that "the adversary ... be between ... ."

PCPs of proximity with highly-efficient verifiers do something that is somewhat similar.