Skip to main content
3 of 4
minor change (removed extra comma)
Dmytro Taranovsky
  • 7.5k
  • 1
  • 22
  • 45

Determinacy and Polynomial Time Degrees

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.

Dmytro Taranovsky
  • 7.5k
  • 1
  • 22
  • 45