Existe alguma classe de complexidade que contenha contrapartes on-line de problemas de otimização?

10

Existe alguma classe de complexidade que contenha contrapartes on-line de problemas de otimização? Caso contrário, como essa classe pode ser definida?

Sabemos que muitos problemas têm sua versão online: por exemplo, versão online do problema de empacotamento de lixeira. Os problemas online são mais difíceis conforme medidos por seus índices competitivos.

E não encontrei nada parecido no zoológico de complexidade .

Essencialmente, poderíamos dizer que não há problemas online, mas apenas algoritmos online para problemas offline. No entanto, se houver problemas online, por que não pode haver uma classe de complexidade que os contenha?

cc.complexity-theory complexity-classes Oleksandr Bondarenko
fonte
Isso está relacionado aos algoritmos de fluxo ( cstheory.stackexchange.com/search?q=stream )?
MS Dousti 25/09/10
11
Os algoritmos on-line não são os mesmos que os algoritmos de fluxo: no fluxo, o fator limitante é o espaço da máquina de fluxo (portanto, ele possui apenas memória de curto prazo). Em algoritmos on-line, o fator limitante é a falta de conhecimento do que está por vir (por isso tem extrema miopia)
Suresh Venkat
@Suresh: Ah, entendo. Obrigado pelo esclarecimento.
MS Dousti 26/09/10

Respostas:

4

Um aspecto complicado da definição de classes de complexidade para problemas on-line é que, em princípio, não há limite para quais tipos de cálculos eu posso fazer depois de ler a entrada. Em outras palavras, os problemas on-line são difíceis, mesmo que eu tenha (por exemplo) um oracle NP processando a entrada assim que ela chegar.

É concebível que, com um processador mais limitado, tarefas de previsão ainda mais simples se tornem mais difíceis de executar, mas, em geral, a dificuldade de projetar algoritmos on-line advém da capacidade do adversário de alterar a entrada depois de criar um modelo de previsão.

Suresh Venkat
fonte
Como nenhum limite para tipos de computação influencia a dureza dos problemas on-line: você poderia, por favor, explicar isso?
Oleksandr Bondarenko
bem, sua classe de complexidade típica é geralmente definida em termos de algum tipo de recurso vinculado. Meu argumento foi que problemas on-line (como o servidor ) são difíceis de uma maneira que não depende de nenhum modelo de complexidade para a máquina subjacente. K
Suresh Venkat
Como o recurso limitado (além do tempo e espaço clássicos) para algoritmos on-line é a informação sobre a instância completa de um determinado problema, se pudéssemos definir de maneira rigorosa a noção de informação para esse fim, poderíamos falar sobre complexidade aulas para problemas online?
Oleksandr Bondarenko
11
você poderia. Não sei se isso foi feito. Suponho que você tenha conferido o livro Borodin / El-Yaniv?
Suresh Venkat
11
Examinei o livro Borodin / El-Yaniv, mas não encontrei nenhuma formalização da noção de informação. No entanto, existem documentos interessantes sobre a complexidade dos conselhos ( scholar.google.com/… ).
Oleksandr Bondarenko
0

Li recentemente o artigo "Jogos contra a natureza" (Papadimitriou, 1985) (aqui está o link: http://www.sciencedirect.com/science/article/pii/0022000085900455 ). Especificamente, este artigo prova que a satisfação estocástica (SSAT) é completa no PSPACE. Eu acho que o SSAT é um problema online? Portanto, este artigo está um pouco relacionado à sua pergunta?

Também estou bastante interessado em questões de complexidade para problemas on-line. Nós podemos discutir!

Cara idiota
fonte