<p>One tricky aspect of defining complexity classes for online problems is that there's in principle no limit on what kinds of computations I can do once I've read the input. In other words, online problems are hard even if I have (for example) an NP oracle processing the input once it arrives. </p>

<p>It's conceivable that with a more limited processor, even simpler prediction tasks become harder to perform, but in general the difficulty of designing online algorithms comes from the ability of the adversary to change the input after you've built a prediction model. </p>

CC BY-SA 2.5
2010-09-25T14:29:30.937Z
How no limit on kinds of computations influences hardness of online problems: could you, please, explain this?
Oleksandr Bondarenko
CC BY-SA 2.5
2010-09-25T15:31:25.010Z
well your typical complexity class is usually defined in terms of some kind of resource bound. My point was that online problems (like $K$-server) are hard in a way that doesn't rely on any model of complexity for the underlying machine.
Suresh Venkat
CC BY-SA 2.5
2010-09-25T16:17:24.313Z
Since the bounded resource (in addition to classical time and space) for online algorithms is the information about the complete instance of a given problem, if we could define the notion of information for this purpose in a rigorous way, then could we talk about complexity classes for online problems?
Oleksandr Bondarenko
CC BY-SA 2.5
2010-09-25T16:46:12.447Z
you could. I'm not aware if this has been done. I assume you've checked the Borodin/El-Yaniv book ?
Suresh Venkat
CC BY-SA 2.5
2010-09-25T18:23:25.057Z
I have looked through the Borodin/El-Yaniv book but haven't found any formalization of the notion of information. However, there are interesting papers on advice complexity (http://scholar.google.com/scholar?hl=en&q=%22advice+complexity%22+%22online+problems%22&btnG=Search&as_sdt=2001&as_ylo=&as_vis=0).
Oleksandr Bondarenko
CC BY-SA 2.5
2010-09-25T14:22:09.300Z
2010-09-25T14:22:09.300Z
Suresh Venkat
<p>I recently read the paper "Games against nature" (Papadimitriou, 1985) (here is the link: <a href="http://www.sciencedirect.com/science/article/pii/0022000085900455" rel="nofollow noreferrer">http://www.sciencedirect.com/science/article/pii/0022000085900455</a>).
Specifically, this paper proves that the Stochastic Satisfiability (SSAT) is PSPACE-complete. I guess the SSAT is an online problem? Thus this paper is somewhat related to your question?</p>

<hr>

<p>I'm also quite interested in complexity issues for online problems. We can discuss!</p>

CC BY-SA 3.0
2017-09-01T02:33:39.147Z
2017-09-01T02:33:39.147Z
zxzx179
<p>Is there known any complexity class containing online counterparts of optimization problems? If not, then how such class can be defined?</p>

<p>We know that many problems have their online version: e.g. online version of bin packing problem. The online problems are harder as measured by their competitive ratios.</p>

<p>And I haven't found anything similar in <a href="http://qwiki.stanford.edu/wiki/Complexity_Zoo">complexity zoo</a>.</p>

<p>Essentially, we could say that there are no online problems, but only online algorithms for offline problems. However, if there are online problems, why there can't be complexity class containing them?</p>

CC BY-SA 2.5
2010-09-25T12:51:32.637Z
Is this related to stream (http://cstheory.stackexchange.com/search?q=stream) algorithms?
Sadeq Dousti
CC BY-SA 2.5
2010-09-25T14:18:31.060Z
Online algorithms are not the same as stream algorithms: in streaming, the limiting factor is the space of the streaming machine (so it has only short-term memory). In online algorithms, the limiting factor is lack of knowledge of what's coming (so it has extreme myopia)
Suresh Venkat
CC BY-SA 2.5
2010-09-26T16:07:57.470Z
@Suresh: Oh, I see. Thanks for the clarification.
Sadeq Dousti
<cc.complexity-theory><complexity-classes>
Is there known any complexity class containing online counterparts of optimization problems?
Oleksandr Bondarenko
# Is there known any complexity class containing online counterparts of optimization problems?

(Asked by: username_0 on 2010-09-25)

Is there known any complexity class containing online counterparts of optimization problems? If not, then how such class can be defined?

We know that many problems have their online version: e.g. online version of bin packing problem. The online problems are harder as measured by their competitive ratios.

And I haven't found anything similar in [complexity zoo](http://qwiki.stanford.edu/wiki/Complexity_Zoo).

Essentially, we could say that there are no online problems, but only online algorithms for offline problems. However, if there are online problems, why there can't be complexity class containing them?

**Tags:** cc.complexity-theory, complexity-classes
> **Comments:**
> **username_1**: Is this related to stream (http://cstheory.stackexchange.com/search?q=stream) algorithms?  
> **username_2**: Online algorithms are not the same as stream algorithms: in streaming, the limiting factor is the space of the streaming machine (so it has only short-term memory). In online algorithms, the limiting factor is lack of knowledge of what's coming (so it has extreme myopia)  
> **username_1**: @Suresh: Oh, I see. Thanks for the clarification.  

---

## 2 answers

### Answer by username_2 on 2010-09-25. Score: 4 | Accepted answer

One tricky aspect of defining complexity classes for online problems is that there's in principle no limit on what kinds of computations I can do once I've read the input. In other words, online problems are hard even if I have (for example) an NP oracle processing the input once it arrives.

It's conceivable that with a more limited processor, even simpler prediction tasks become harder to perform, but in general the difficulty of designing online algorithms comes from the ability of the adversary to change the input after you've built a prediction model.

> **Comments:**
> **username_0**: How no limit on kinds of computations influences hardness of online problems: could you, please, explain this?  
> **username_2**: well your typical complexity class is usually defined in terms of some kind of resource bound. My point was that online problems (like $K$-server) are hard in a way that doesn't rely on any model of complexity for the underlying machine.  
> **username_0**: Since the bounded resource (in addition to classical time and space) for online algorithms is the information about the complete instance of a given problem, if we could define the notion of information for this purpose in a rigorous way, then could we talk about complexity classes for online problems?  
> **username_2**: you could. I'm not aware if this has been done. I assume you've checked the Borodin/El-Yaniv book ?  
> **username_0**: I have looked through the Borodin/El-Yaniv book but haven't found any formalization of the notion of information. However, there are interesting papers on advice complexity (http://scholar.google.com/scholar?hl=en&q=%22advice+complexity%22+%22online+problems%22&btnG=Search&as_sdt=2001&as_ylo=&as_vis=0).  

---

### Answer by username_3 on 2017-09-01. Score: 0

I recently read the paper "Games against nature" (Papadimitriou, 1985) (here is the link: <http://www.sciencedirect.com/science/article/pii/0022000085900455>).
Specifically, this paper proves that the Stochastic Satisfiability (SSAT) is PSPACE-complete. I guess the SSAT is an online problem? Thus this paper is somewhat related to your question?

---

I'm also quite interested in complexity issues for online problems. We can discuss!


---

