10
$\begingroup$

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.

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?

$\endgroup$
  • $\begingroup$ Is this related to stream (cstheory.stackexchange.com/search?q=stream) algorithms? $\endgroup$ – M.S. Dousti Sep 25 '10 at 12:51
  • 1
    $\begingroup$ 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) $\endgroup$ – Suresh Venkat Sep 25 '10 at 14:18
  • $\begingroup$ @Suresh: Oh, I see. Thanks for the clarification. $\endgroup$ – M.S. Dousti Sep 26 '10 at 16:07
4
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ How no limit on kinds of computations influences hardness of online problems: could you, please, explain this? $\endgroup$ – Oleksandr Bondarenko Sep 25 '10 at 14:29
  • $\begingroup$ 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. $\endgroup$ – Suresh Venkat Sep 25 '10 at 15:31
  • $\begingroup$ 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? $\endgroup$ – Oleksandr Bondarenko Sep 25 '10 at 16:17
  • 1
    $\begingroup$ you could. I'm not aware if this has been done. I assume you've checked the Borodin/El-Yaniv book ? $\endgroup$ – Suresh Venkat Sep 25 '10 at 16:46
  • 1
    $\begingroup$ 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 (scholar.google.com/…). $\endgroup$ – Oleksandr Bondarenko Sep 25 '10 at 18:23
0
$\begingroup$

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!

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.