# Is there an online algorithm for solving any P-complete problem?

We can think of the class $NC$ as the class of problems that can be solved in parallel, whereas a $P$-complete problem probably has no parallel solution. My question is: where do online algorithms fit in this spectrum?

My intuition says that online problems are more difficult than parallel problems. This would be more-or-less confirmed by the existence of an online algorithm for a $P$-complete problem. So do any exist?

Alternatively, we could define a complexity class for online problems $O$ such that: $$NC \subseteq O \subseteq P$$ Then we would have to define $O$-complete problems and convince ourselves that they cannot be parallelized.

• Monoid computations that take constant time are complete in $NC^1$ and they can be done online. In my experience, other problems that I've found in $NC$ also have reasonable online algorithms by a similar argument. Basically, each new data point is a new, independent branch in the algorithm. I'm certainly open to the possibility of there being an $NC$ algorithm that can't be made online, my intuition just says "probably not." – Mike Izbicki Aug 28 '13 at 16:32
• I'm wondering what a reasonable computation model for such a class would look like. A DTM with a work tape of $log(n)$ length where each chunk of the input is written successively after some state "next_chunk" is entered. The work tape should probably not require more than $O(log(n))$ space. Now for time measurement we could analyze the worst-cast of how many steps it takes to before the "next_chunk" state is entered again(e.g. denoted by $T(n)$) now $\frac{n}{log(n)} T(n)$ can be used to relate it to the generic TIME class – John D. Aug 28 '13 at 18:46
• The graph of an explicit strong extractor can be computed in $P$, but if $\:k,\epsilon,d,m\:$ are all small then it can't be computed by an online algorithm. $\;\;\;$ – user6973 Aug 28 '13 at 20:05