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 5^{11^7}$, Hercules must choose between two heads, either $3$ or $7$. If he decapitates $2^{{19}^3}$, the Hydra becomes $s^{19} \cdot 5^{11^7}$, where $s = p \cdot q \cdots$ is a square-free number relatively prime to the co-product of the prime number it replaces (so not divisible by $5$ in this case), expanding to $p^{19} \cdot q^{19} \cdots 5^{11^7}$. 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, every Hydra (every number) 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 $\text{MO}:\mathbb{N}^3 \rightarrow \mathbb{N}$ 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}(n)$, $\text{He}(n)$, and $\text{Hy}(n)$ are all required to be computable in subexponential $2^{o(\log_2{n})} = n^{o(1)}$ time, $\text{I}(n) = \text{I}(2^{\lfloor \log_2{n} \rfloor}) > n$ for all $n$ (we only care about its values on powers of $2$), and that $\text{He}$ and $\text{Hy}$ always output a correct move if possible. Now 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 it's not possible, 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 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, since in general it won't be the case that $q \cdot r \in \text{I}(\mathbb{N})$, and it's plausible that chaining them all together results in an exponential-time algorithm. For every $k$ there would be a subexponential-time algorithm to find $k$ prime factors of $x \in \text{I}(\mathbb{N})$, but no subexponential-time algorithm to factor $x$.
Second question: Is this reasoning correct, and is it actually possible for there to exist such a prime divisor finding algorithm relative to any 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
$\text{MO}(p^{q^ r \cdot y} \cdot x, ~p^{q^r} = \text{He}(p^{q^ r \cdot y} \cdot x), ~s = \text{Hy}(p^{q^ r \cdot y} \cdot x, ~p^{q^r})) = s^{q \cdot y} \cdot x = t^{q \cdot y} \cdot u^{q \cdot y} \cdots x$
with $s = t \cdot u \cdots$ square-free and $t, u, \dots$ all prime and not dividing $x$.
Third question: Can Hercules win from this position under these assumptions?
A winning move is $t^q$, but maybe he can't find $t$ in time. However, even in that case, maybe he can find some other prime divisor of the game instance and keep going. I think he possibly can, but it starts to get more complicated from this point. If the assumptions are unnecessarily strong, I'd like to alter them to explore this case. One option is to give Hercules a memory that he has access to in subsequent rounds, so he might be able to find some other factors of the instance while he's not busy factoring the exponent of $p$. Another idea is to constrain $\text{MO}(n = p^{q^r \cdot y} \cdot x, ~p^{q^r}, ~\text{Hy}(\dots))$ and $\text{I}(n)$ in an identical way, then if Hercules could get to this point in the game by finding a prime divisor he could also get past it for the same reason.
Also, I'd appreciate any references to other versions of this problem.
