# Is $\mathsf{P} = \mathsf{NP}$ relative to a universal predictor?

Consider any language $L$. Define $s(L) \in {\lbrace 0, 1 \rbrace}^\omega$ (an infinite sequence of bits) by the recursive formula

$$s(L)_n=\chi_L(s(L)_{<n})$$

Here $\chi_L$ is the characteristic function of $L$ i.e. $\chi_L(w)=1$ for $w \in L$, $\chi_L(w)=0$ for $w \notin L$

A language $U$ is called a "universal (closed) predictor" when

$$\forall L \in \mathsf{P} \, \forall n>>0:s(L)_n=\chi_U(s(L)_{<n})$$

It is easy to see $U \notin \mathsf{P}$ by considering $L = U^c$. However, $U$ can be recursive. To give an example, consider the language decided by the following algorithm $A$. Given input $w$, $A$ runs all possible programs in shortlex order, allowing each to execute for time $t(|w|)$ where $t$ is a function of superpolynomial growth. Once it reaches a program $R$ that outputs $w$ plus one or more bits and doesn't halt, $A$ outputs the first bit $R$ outputted after $w$. It easy easy to see that (under mild conditions on $t$) $A$ always halts and the language it decides is a universal predictor. $A's$ time complexity is approximately $2^nt(n)$

Given $a \in {\lbrace 0, 1 \rbrace}^\omega$, define $s(L, a)$ by

$$s(L, a)_{2n} = \chi_L(s(L, a)_{<2n})$$ $$s(L, a)_{2n + 1} = a_n$$

A language $V$ is called a "universal open predictor" when

1. $\forall w \in V : |w|$ is even
2. $\forall L \in \mathsf{P}, a \in {\lbrace 0, 1 \rbrace}^\omega \, \forall n>>0:s(L, a)_{2n}=\chi_V(s(L, a)_{<2n})$

[I am using 0-based indices so $|s_{<2n}| = 2n$]

Again it is easy to see $V \notin \mathsf{P}$ but $V$ can be in $\mathsf{E}$

Is there $V$ a universal open predictor s.t. $\mathsf{P}^V=\mathsf{NP}^V$?

I'm especially interested in having either a specific example of such $V$ or a proof such $V$ doesn't exist under reasonable assumptions such as $\mathsf{P} \ne \mathsf{NP}$

The question might seem strange, so I'll briefly outline my motivation for it. I'm interested in AIXI-like models of aritifical intelligence. Here $L$ plays the role of the environment, which I assume to be efficiently computable, and $a$ plays the role of the actions of the agent itself. Given a positive answer for my question, it is possible to construct an agent efficiently computable relative to $V$ which optimizes a given efficiently computable utility function $u$ by choosing its future actions s.t. $u$ is maximized assuming the environment behaves according to the prediction of $V$

• In terms of relativization point of view, V=PSPACE works. – Tayfun Pay Feb 16 '13 at 22:37