Sign up ×
Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.

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


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$

share|cite|improve this question
In terms of relativization point of view, V=PSPACE works. – Tayfun Pay Feb 16 '13 at 22:37

1 Answer 1

up vote 5 down vote accepted

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|11x: 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<2n)≠χW(s<2n), 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 ∪ (VT). 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 PW = NPW = EXPSPACE. This concludes that W satisfies the desired property.

share|cite|improve this answer
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 but Legg avoids time complexity considerations – Squark Feb 16 '13 at 22:00
@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 Feb 16 '13 at 22:45
@Squark: I thought more. :) – Tsuyoshi Ito Feb 16 '13 at 23:08
OK, this is not a technicality. Thx! – Squark Feb 17 '13 at 20:31

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.