The game of Hercules vs. the Hydra can be put in terms of a single number in hereditarily-factorized form. For example, if the Hydra is $ 2^{{19}^3 \cdot {11}^{7}}$ , Hercules must choose between two heads, either $ 3$ or $ 7$ . If he decapitates $ 2^{{19}^3}$ , the Hydra becomes $ s^{19 \cdot {11}^7}$ , where $ s$ is a square-free number chosen by the Hydra, expanding to $ p^{19 \cdot 11^7} \cdot q^{19 \cdot 11^7} \cdots$ . On the next turn Hercules wins by choosing $ p^{19}$ ; since $ 19$ isn’t the exponent of an exponent the Hydra has no moves and dies. By Goodstein’s theorem, the Hydra eventually dies no matter what heads Hercules chooses.

I’m considering a resource-bounded version of this game. Let $ \text{I}:\mathbb{N}\rightarrow\mathbb{N}$ be a computable function that generates a game instance. Hercules will be modeled by a computable function $ \text{He}:\mathbb{N}\rightarrow \mathbb{N}$ which given a game returns a path to a head, for example $ 2^{{19}^3}$ in the example above. And the Hydra is a computable function $ \text{Hy}:\mathbb{N} \times \mathbb{N} \rightarrow \mathbb{N}$ which given the same game and the output of Hercules returns a square-free number to be substituted two levels below the head. The actual substitution that produces the next round of the game happens somewhere up on Mount Olympus, since except in certain cases it makes the game much larger and can’t be done with reasonable time constraints.

Suppose $ \text{I}$ , $ \text{He}$ , and $ \text{Hy}$ are all required to be computable in subexponential ($ 2^{o(n)}$ ) time and to output a correct move if possible, and consider the same question, can Hercules slay the Hydra? That is, given $ \text{I}$ and $ \text{Hy}$ , is there a $ \text{He}$ that can win every game instance in $ \text{I}(\mathbb{N})$ ?

If $ \text{FACTORING} \in \text{DTIME}(2^{o(n)})$ , then clearly yes. Hercules can factor the game, recover the tree representation, and select a valid move in every case.

Now suppose $ \text{FACTORING} \notin \text{DTIME}(2^{o(n)})$ . I believe it is an open problem to determine whether or not it is possible to find a prime larger than $ 2^k$ in $ 2^{o(k)}$ time with a factoring oracle. If not, then sufficiently large numbers generated by any algorithm in subexponential time have all factors subexponential and Hercules can find them and win anyway.

First question: is this reasoning correct, and is this problem in fact open? In any case, is my claim correct that there is no obvious reason that $ \text{FACTORING} \notin \text{DTIME}(2^{o(n)})$ should imply that for some game instance generator $ \text{I}$ , no Hercules can win every game in $ \text{I}(\mathbb{N})$ ?

So, let’s assume not only that hard instances exist, but that they are possible to generate, and in particular that there is no subexponential-time algorithm to factor $ \text{I}(\mathbb{N})$ . As far as I can tell, even in this situation it is still possible that that there is a subexponential-time algorithm to find a single prime divisor of a game instance. We could use this to factor semi-primes, and given $ p \cdot q \cdot r$ we could find $ p$ and also $ q \cdot r$ , but it won’t work recursively to factor $ q \cdot r$ — we’ll need a different subexponential-time algorithm for that and it’s plausible that chaining them all together results in an exponential-time algorithm.

Second question: is this reasoning correct, and is it actually possible for there to exist such a prime divisor finding algorithm relative to any particular hard factorization instance generator?

If Hercules can find a prime divisor $ p$ of the initial game instance, he can make progress, since while the game itself can’t be factored, the exponent of $ p$ can, and by choosing heads rooted at $ p$ he can eventually reduce the Hydra to the form $ p^{q^ r \cdot y} \cdot x$ with $ p$ , $ q$ , $ r$ all prime. Hercules then chooses $ p^{q^r}$ , and the game becomes $ s^{q \cdot y} \cdot x$ with square-free $ s = t \cdot u \cdots$ , expanding to $ t^{q \cdot y} \cdot u^{q \cdot y} \cdots x$ .

Third question: Can Hercules still win from this position under these assumptions? A winning move is $ t^q$ , but maybe he can’t find $ t$ in time. Can he still find some other prime divisor of the game instance and keep going? I think he probably can, but it starts to get more complicated from this point.

Also I’d appreciate any references to other versions of Hercules and the Hydra with time constraints.