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?

  • 3
    $\begingroup$ What causes you to suggest that there is an online algorithm for every problem in NC? $\endgroup$ Aug 28, 2013 at 13:48
  • $\begingroup$ 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." $\endgroup$ Aug 28, 2013 at 16:32
  • $\begingroup$ 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 $\endgroup$
    – John D.
    Aug 28, 2013 at 18:46
  • 2
    $\begingroup$ What does it mean for a decision problem to have an online algorithm? $\endgroup$ Aug 28, 2013 at 18:57
  • 1
    $\begingroup$ 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. $\;\;\;$ $\endgroup$
    – user6973
    Aug 28, 2013 at 20:05


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.