<p>I am not familiar with the notion of universal predictor, and I did not follow everything you wrote; in particular, I did not follow your sketch of the proof of existence of a universal predictor in E.  But assuming that there exists a universal open predictor that belongs to E, the answer to your question is positive.  And I am afraid that you will probably be disappointed by the reason.</p>

<p><em>Edit in revision 2: I changed the construction in response to the added restriction in revision 2 of the question, but the general idea is the same: mix a hard language into a universal open predictor in such a way that the definition of universal open predictor does not notice the difference.</em></p>

<p>Let <i>T</i> = {0<sup>|<i>x</i>|</sup>11<i>x</i>: <i>x</i>∈{0,1}<sup>*</sup>}.  Note that every word in <i>T</i> has an even length.  An important property of <i>T</i> is that no word in <i>T</i> is a proper prefix of another word in <i>T</i>.  This implies that if the symmetric difference between two languages <i>V</i> and <i>W</i> is contained in <i>T</i>, then for every infinite sequence <i>s</i>∈{0,1}<sup>ω</sup>, there is at most one <i>n</i> such that χ<sub><i>V</i></sub>(<i>s</i><sub>&lt;2<i>n</i></sub>)≠χ<sub><i>W</i></sub>(<i>s</i><sub>&lt;2<i>n</i></sub>), and in particular <i>V</i> is a universal open predictor if and only if <i>W</i> is a universal open predictor.</p>

<p>It is easy to see that there exists an EXPSPACE-complete language which is a subset of <i>T</i>.  Let <i>L</i> be such a language.  Let <i>V</i> be a universal open predictor that belongs to E, and hence also to EXPSPACE.  Define a language <i>W</i> = <i>L</i> ∪ (<i>V</i>∖<i>T</i>).  Because <i>V</i> is a universal open predictor and the symmetric difference between <i>V</i> and <i>W</i> is contained in <i>T</i>, <i>W</i> is also a universal open predictor.  It is easy to see that <i>W</i> is EXPSPACE-complete, and therefore P<sup><i>W</i></sup> = NP<sup><i>W</i></sup> = EXPSPACE.  This concludes that <i>W</i> satisfies the desired property.</p>

CC BY-SA 3.0
2013-02-16T22:00:40.760Z
Ha! Good point, but you caught me on a technicality. I corrected the definition to state that a universal open predictor has only even-length words.
"Universal predictor" is my own terminology. The concept is inspired by http://arxiv.org/abs/cs/0606070 but Legg avoids time complexity considerations
Vanessa
CC BY-SA 3.0
2013-02-16T22:45:12.727Z
@Squark: Hmm, I _guess_ that the idea of mixing in a hard language works also with the revised definition and therefore I _guess_ that this is not just a technicality, but I have to think more.
Tsuyoshi Ito
CC BY-SA 3.0
2013-02-16T23:08:40.327Z
@Squark: I thought more. :)
Tsuyoshi Ito
CC BY-SA 3.0
2013-02-17T20:31:50.003Z
OK, *this* is not a technicality. Thx!
Vanessa
CC BY-SA 3.0
2013-02-16T21:31:10.177Z
2013-02-17T05:18:22.463Z
2013-02-17T05:18:22.463Z
Tsuyoshi Ito
<p>Consider any language $L$. Define $s(L) \in {\lbrace 0, 1 \rbrace}^\omega$ (an infinite sequence of bits) by the recursive formula</p>

<p>$$s(L)_n=\chi_L(s(L)_{&lt;n})$$</p>

<p>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$</p>

<p>A language $U$ is called a "universal (closed) predictor" when</p>

<p>$$\forall L \in \mathsf{P} \, \forall n&gt;&gt;0:s(L)_n=\chi_U(s(L)_{&lt;n})$$</p>

<p>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)$</p>

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

<p>$$s(L, a)_{2n} = \chi_L(s(L, a)_{&lt;2n})$$
$$s(L, a)_{2n + 1} = a_n$$</p>

<p>A language $V$ is called a "universal open predictor" when </p>

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

<p>[I am using 0-based indices so $|s_{&lt;2n}| = 2n$]</p>

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

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

<p>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}$</p>

<p>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$</p>

CC BY-SA 3.0
2013-02-16T22:37:59.397Z
In terms of relativization point of view, V=PSPACE works.
Tayfun Pay
<cc.complexity-theory><ai.artificial-intel><p-vs-np><relativization>
Is $\mathsf{P} = \mathsf{NP}$ relative to a universal predictor?
Vanessa
# Is $\mathsf{P} = \mathsf{NP}$ relative to a universal predictor?

(Asked by: username_0 on 2013-02-15)

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)\_{

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)\_{

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$

**Tags:** cc.complexity-theory, ai.artificial-intel, p-vs-np, relativization

> **Comments:**
> **username_1**: In terms of relativization point of view, V=PSPACE works.  

---

## 1 answers

### Answer by username_2 on 2013-02-16. Score: 5 | Accepted answer

I am not familiar with the notion of universal predictor, and I did not follow everything you wrote; in particular, I did not follow your sketch of the proof of existence of a universal predictor in E. But assuming that there exists a universal open predictor that belongs to E, the answer to your question is positive. And I am afraid that you will probably be disappointed by the reason.

*Edit in revision 2: I changed the construction in response to the added restriction in revision 2 of the question, but the general idea is the same: mix a hard language into a universal open predictor in such a way that the definition of universal open predictor does not notice the difference.*

Let *T* = {0|*x*|11*x*: *x*∈{0,1}\*}. Note that every word in *T* has an even length. An important property of *T* is that no word in *T* is a proper prefix of another word in *T*. This implies that if the symmetric difference between two languages *V* and *W* is contained in *T*, then for every infinite sequence *s*∈{0,1}ω, there is at most one *n* such that χ*V*(*s*<2*n*)≠χ*W*(*s*<2*n*), and in particular *V* is a universal open predictor if and only if *W* is a universal open predictor.

It is easy to see that there exists an EXPSPACE-complete language which is a subset of *T*. Let *L* be such a language. Let *V* be a universal open predictor that belongs to E, and hence also to EXPSPACE. Define a language *W* = *L* ∪ (*V*∖*T*). Because *V* is a universal open predictor and the symmetric difference between *V* and *W* is contained in *T*, *W* is also a universal open predictor. It is easy to see that *W* is EXPSPACE-complete, and therefore P*W* = NP*W* = EXPSPACE. This concludes that *W* satisfies the desired property.

> **Comments:**
> **username_0**: Ha! Good point, but you caught me on a technicality. I corrected the definition to state that a universal open predictor has only even-length words. "Universal predictor" is my own terminology. The concept is inspired by http://arxiv.org/abs/cs/0606070 but Legg avoids time complexity considerations  
> **username_2**: @Squark: Hmm, I _guess_ that the idea of mixing in a hard language works also with the revised definition and therefore I _guess_ that this is not just a technicality, but I have to think more.  
> **username_2**: @Squark: I thought more. :)  
> **username_0**: OK, *this* is not a technicality. Thx!  

---

