Determinacy and polynomial time degrees

Question

Is there a function $f:2^{<ℕ}→\{0,1\}$ such that for all $X∈{2^ℕ}$ with $X_{2i+1}=f(X_0,...,X_i)$ all hyperarithmetical properties of the polynomial time degree of $X$ are independent of $X$?

The polynomial time degree of $X$ is the set of languages that are computable in polynomial time using $X$ as an oracle ($X_i$ can be queried with $i$ in binary). A variation on the question is to use $X_{i+2}$ in place of $X_{2i+1}$.

A consequence of definable determinacy is that all sufficiently high Turing degrees are equivalent with respect to definable properties. The scope of 'definable' depends on how much determinacy is assumed; Borel determinacy is provable in ZFC. The indistinguishability also applies to elementary time degrees. However, it fails for polynomial time degrees: Relativized P=NP toggles for arbitrarily high degrees.

To avoid this counterexample, the question requires the oracle not only to be sufficiently powerful, but also sufficiently closed with respect to initial segments of itself. As a result, the relativized P=PSPACE holds (i.e. there is $f$ such that for all $X$, the relativized P=PSPACE holds; the query tape counts against space usage; also, using a form of join between $f$, degree properties that hold for all $X$ form a directed system). However, the proof of indistinguishability of sufficiently high Turing degrees using determinacy does not appear to work, so there might be a more subtle property that toggles. Recall that in the proof, given a strategy $S$ for player I, player II can make the play have an arbitrary Turing degree $≥S$ and vice versa, so by determinacy, all sufficiently high degrees are indistinguishable. This does not work for polynomial time degrees because playing a code for $S$ takes exponential time.

Answer 1

Yes, and with a proper indexing, this also holds for a very restricted type of reduction called the prefix reduction: $X≤Y ⇔ ∃a ∀s (X_s ⇔ Y_{a⌢s})$ ('$⌢$' is string concatenation), with the equivalence classes forming the prefix degrees.

Let us say that $X$ is $f$-closed iff $∃a ∀s \, f(X_t:t<s) = X_{a⌢s}$ (this choice is somewhat arbitrary if $f$ is not sufficiently universal; '$<$' treats $s$ and $t$ as numbers). Using determinacy (below), there is a $Δ^1_2$ $f$ such that all $f$-closed prefix degrees have the same arithmetic properties. This extends to other properties to the extent that we have determinacy ($f$ need not be $Δ^1_2$ and depends on the property as there are uncountably many of them).

For the proof, consider a length $ω$ game on $\{0,1\}$ using a prefix-degree invariant payoff set $T$, with the play $P$; $P_{i⌢s}$ iff player $i+1$ chose 1 on move $s$. Without loss of generality, assume that player I has a winning strategy $S$. Define $f$ to encode the resulting play if player I uses $S$ and player II plays $X$ (ignoring player I). Given an $f$-closed $X$, the play has the same prefix degree as $X$. Thus, player II can cause the play to have any $f$-closed prefix degree, so all such degrees satisfy $T$.

Complexity Classes

For every $f$ and $g$, there is an $f$-closed prefix degree that is $\text{E}^{f,g}$-complete under polynomial time linear space Turing reductions. ($\text{E}^A$ consists of all decision problems that can be solved in time $2^{O(n)}$ with an oracle for $A$.) Thus, for all $A$ of sufficiently high degree, the arithmetic properties of $\text{E}^A$ are independent of $A$.

Determinacy thus gives a powerful tool for resolving questions about such degrees. For example, using determinacy, for every sufficiently-closed prefix degree $B$, there is a (non-unique) 'logarithm' $A$ with $B$ being $\text{E}^A$-complete. Also, the invariance for $\text{E}^A$ gives a sharp limit on the relativization possibilities — possibilities that are central to computational complexity theory and to our lack of progress in it.

Also, while arithmetic properties of $A$ are independent from $A$ for every sufficiently closed polynomial time degree $A$, it is not enough that $A$ is high enough and $\text{P}^A = \text{PSPACE}^A$. The reason is that for a random oracle $C$ (dependent on $A$), and every strong enough pseudorandom function $f$ (independent of $A$), $f(C_0,...,C_{2^n})$ is not in $\text{SPACE}(2^{o(n)})^{A,C}$ (there are too many possibilities for $C$ for $2^{2^{o(n)}}$ bits of advice). The use of $\text{EXP}^A$ (or $\text{E}^A$ for polynomial time linear space degrees) is thus close to optimal.