<p>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?</p>

<p>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?</p>

<p>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.</p>

<p>Any advice on what I should read to think about this some more?</p>

CC BY-SA 3.0
2013-08-28T13:48:50.910Z
What causes you to suggest that there is an online algorithm for every problem in NC?
András Salamon
CC BY-SA 3.0
2013-08-28T16:32:19.783Z
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
CC BY-SA 3.0
2013-08-28T18:46:50.230Z
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.
CC BY-SA 3.0
2013-08-28T18:57:06.173Z
What does it mean for a decision problem to have an online algorithm?
Robin Kothari
CC BY-SA 3.0
2018-04-27T14:54:59.740Z
You may be interested in https://www.sciencedirect.com/science/article/pii/S0020019012002980 -- _Online integer packing with recourse_. If I recall, they give constant-competitive algorithms for some integer linear programs. The algorithms are online with recourse (they can change a limited number of their decisions retroactively), while the offline problem is NP-hard and has no poly-time constant approximation algorithms unless P=NP.
Neal Young
CC BY-SA 3.0
2018-04-27T14:55:38.940Z
similar question here: https://cstheory.stackexchange.com/questions/40669/is-there-any-online-problem-that-the-best-known-competitive-ratio-is-better-than .  p.s. Hi Mike!
Neal Young
<reference-request><complexity-classes><online-algorithms>
Is there an online algorithm for solving any P-complete problem?
Mike Izbicki
# Is there an online algorithm for solving any P-complete problem?

(Asked by: username_0 on 2013-08-28)

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?

**Tags:** reference-request, complexity-classes, online-algorithms
> **Comments:**
> **username_1**: What causes you to suggest that there is an online algorithm for every problem in NC?  
> **username_0**: 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."  
> **username_2**: 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  
> **username_3**: What does it mean for a decision problem to have an online algorithm?  
> **username_4**: You may be interested in https://www.sciencedirect.com/science/article/pii/S0020019012002980 -- _Online integer packing with recourse_. If I recall, they give constant-competitive algorithms for some integer linear programs. The algorithms are online with recourse (they can change a limited number of their decisions retroactively), while the offline problem is NP-hard and has no poly-time constant approximation algorithms unless P=NP.  
> **username_4**: similar question here: https://cstheory.stackexchange.com/questions/40669/is-there-any-online-problem-that-the-best-known-competitive-ratio-is-better-than .  p.s. Hi Mike!  

---

## 0 answers

