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.Any advice on what I should read to think about this some more?
Is there an online algorithm for solving any P-complete problem?
reference request;complexity classes;online algorithms