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?

Improve this question
$\endgroup$
3
  • $\begingroup$ Is this related to stream (cstheory.stackexchange.com/search?q=stream) algorithms? $\endgroup$
    – Sadeq Dousti
    Sep 25, 2010 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, 2010 at 14:18
  • $\begingroup$ @Suresh: Oh, I see. Thanks for the clarification. $\endgroup$
    – Sadeq Dousti
    Sep 26, 2010 at 16:07

2 Answers 2

Reset to default
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.

Improve this answer
$\endgroup$
5
  • $\begingroup$ How no limit on kinds of computations influences hardness of online problems: could you, please, explain this? $\endgroup$
    – Oleksandr Bondarenko
    Sep 25, 2010 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, 2010 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, 2010 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, 2010 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, 2010 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!

Improve this answer
$\endgroup$

Your Answer

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

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