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


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

Fix $\mathsf{X} \subset 2^{{\lbrace 0, 1 \rbrace}^*}$ a set of languages, typically a complexity class

A language $U$ is called an $\mathsf{X}$-predictor when

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

It is easy to see $U \notin \mathsf{X}$ by considering $K = U^c$. In particular, given $\mathsf{Y} \subset 2^{{\lbrace 0, 1 \rbrace}^*}$, $U \in \mathsf{Y}$ implies $\mathsf{X} \ne \mathsf{Y}$

I am interested to know whether there is an $\mathsf{L}$-predictor in $\mathsf{P}$. Obviously if true it would very difficult to prove since it would imply $\mathsf{L} \ne \mathsf{P}$. However it might be feasible to either prove it under assumptions such as $\mathsf{L} \ne \mathsf{P}$ or prove the converse or at least provide some evidence to one side or other

What is the evidence for/against the existence of an $\mathsf{L}$-predictor in $\mathsf{P}$?

EDIT: There is a weaker type of predictor the existence of which also implies $\mathsf{L} \ne \mathsf{P}$. Define $s'(K) \in {\lbrace 0, 1 \rbrace}^\omega$ by the formula


$U_w$ is called a weak $\mathsf{L}$-predictor when

$$\forall K \in \mathsf{L} \, \forall n>>0:s'(K)_n=\chi_{U_w}(s'(K)_{<n})$$

It's easy to see that any $\mathsf{L}$-predictor is (in particular) a weak $\mathsf{L}$-predictor. However this definition is weaker since when the sequence $s(K)$ is computed, $s(K)_{<n}$ serves as a state of the process of linear size in $n$. On the other hand when $s'(K)$ is computed, we're bounded by the logarithmic size state allowed for deciding $K$

$U_w \in \mathsf{P}$ implies $\mathsf{L} \ne \mathsf{P}$ since it's easy to see that if $\mathsf{L} = \mathsf{P}$ then a weak $\mathsf{L}$-predictor is a $\mathsf{P}$-predictor

What is the evidence for/against the existence of a weak $\mathsf{L}$-predictor in $\mathsf{P}$?

As a sidenote, $U_w \in \mathsf{P}$ also implies that there is a polynomial $p(n)$ such that any $K \in \mathsf{TALLY} \cap \mathsf{L}$ can be decided in time $t_K(n)$ with $t_K(n) < p(n)$ for $n >> 0$

Actually proving that there is no $\mathsf{L}$-predictor in $\mathsf{P}$ must also be very difficult since it would imply $\mathsf{P} \ne \mathsf{PSPACE}$. This is so since it's possible to construct an $\mathsf{L}$-predictor in $\mathsf{PSPACE}$, analogously to the construction of a $\mathsf{P}$-predictor in $\mathsf{E}$ given here


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.