Existe-t-il une classe de complexité contenant des homologues en ligne de problèmes d'optimisation?

10

Existe-t-il une classe de complexité contenant des homologues en ligne de problèmes d'optimisation? Sinon, comment définir une telle classe?

Nous savons que de nombreux problèmes ont leur version en ligne: par exemple, la version en ligne du problème d'emballage de bac. Les problèmes en ligne sont plus difficiles à mesurer d'après leurs ratios compétitifs.

Et je n'ai rien trouvé de similaire dans le zoo de complexité .

Essentiellement, nous pourrions dire qu'il n'y a pas de problèmes en ligne, mais uniquement des algorithmes en ligne pour les problèmes hors ligne. Cependant, s'il y a des problèmes en ligne, pourquoi ne peut-il y avoir de classe de complexité les contenant?

cc.complexity-theory complexity-classes Oleksandr Bondarenko
la source
Est-ce lié aux algorithmes de flux ( cstheory.stackexchange.com/search?q=stream )?
MS Dousti
1
Les algorithmes en ligne ne sont pas les mêmes que les algorithmes de flux: en streaming, le facteur limitant est l'espace de la machine de streaming (donc elle n'a que de la mémoire à court terme). Dans les algorithmes en ligne, le facteur limitant est le manque de connaissances sur ce qui s'en vient (il a donc une myopie extrême)
Suresh Venkat
@Suresh: Oh, je vois. Merci pour la clarification.
MS Dousti

Réponses:

4

Un aspect délicat de la définition des classes de complexité pour les problèmes en ligne est qu'il n'y a en principe aucune limite sur les types de calculs que je peux faire une fois que j'ai lu l'entrée. En d'autres termes, les problèmes en ligne sont difficiles même si j'ai (par exemple) un oracle NP traitant l'entrée une fois arrivée.

Il est concevable qu'avec un processeur plus limité, des tâches de prédiction encore plus simples deviennent plus difficiles à effectuer, mais en général, la difficulté de concevoir des algorithmes en ligne vient de la capacité de l'adversaire à modifier l'entrée après avoir construit un modèle de prédiction.

Suresh Venkat
la source
Comment aucune limite sur les types de calculs n'influence la dureté des problèmes en ligne: pourriez-vous, s'il vous plaît, expliquer cela?
Oleksandr Bondarenko
K
Étant donné que la ressource limitée (en plus du temps et de l'espace classiques) pour les algorithmes en ligne est l'information sur l'instance complète d'un problème donné, si nous pouvions définir la notion d'information à cette fin de manière rigoureuse, alors pourrions-nous parler de complexité des cours pour les problèmes en ligne?
Oleksandr Bondarenko,
1
vous pourriez. Je ne sais pas si cela a été fait. Je suppose que vous avez vérifié le livre Borodin / El-Yaniv?
Suresh Venkat
1
J'ai parcouru le livre Borodin / El-Yaniv mais je n'ai trouvé aucune formalisation de la notion d'information. Cependant, il existe des articles intéressants sur la complexité des conseils ( scholar.google.com/… ).
Oleksandr Bondarenko
0

J'ai récemment lu le document "Games against nature" (Papadimitriou, 1985) (voici le lien: http://www.sciencedirect.com/science/article/pii/0022000085900455 ). Plus précisément, cet article prouve que la satisfaction stochastique (SSAT) est PSPACE-complete. Je suppose que le SSAT est un problème en ligne? Cet article est donc quelque peu lié à votre question?

Je suis également très intéressé par les problèmes de complexité des problèmes en ligne. Nous pouvons discuter!

Mec idiot
la source