¿Se conoce alguna clase de complejidad que contenga homólogos en línea de problemas de optimización?

10

¿Se conoce alguna clase de complejidad que contenga homólogos en línea de problemas de optimización? Si no, ¿cómo se puede definir esa clase?

Sabemos que muchos problemas tienen su versión en línea: por ejemplo, la versión en línea del problema de empaquetado de contenedores. Los problemas en línea son más difíciles según lo medido por sus relaciones competitivas.

Y no he encontrado nada similar en el complejo zoológico .

Esencialmente, podríamos decir que no hay problemas en línea, sino solo algoritmos en línea para problemas fuera de línea. Sin embargo, si hay problemas en línea, ¿por qué no puede haber una clase de complejidad que los contenga?

cc.complexity-theory complexity-classes Oleksandr Bondarenko
fuente
¿Está esto relacionado con los algoritmos de transmisión ( cstheory.stackexchange.com/search?q=stream )?
MS Dousti
1
Los algoritmos en línea no son lo mismo que los algoritmos de transmisión: en la transmisión, el factor limitante es el espacio de la máquina de transmisión (por lo que solo tiene memoria a corto plazo). En los algoritmos en línea, el factor limitante es la falta de conocimiento de lo que viene (por lo que tiene una miopía extrema)
Suresh Venkat
@Suresh: Oh, ya veo. Gracias por la aclaración.
MS Dousti

Respuestas:

4

Un aspecto complicado de definir clases de complejidad para problemas en línea es que, en principio, no hay límite en los tipos de cálculos que puedo hacer una vez que he leído la entrada. En otras palabras, los problemas en línea son difíciles incluso si tengo (por ejemplo) un oráculo NP que procesa la entrada una vez que llega.

Es concebible que con un procesador más limitado, las tareas de predicción incluso más simples se vuelvan más difíciles de realizar, pero en general la dificultad de diseñar algoritmos en línea proviene de la capacidad del adversario para cambiar la entrada después de haber construido un modelo de predicción.

Suresh Venkat
fuente
Cómo ningún límite en los tipos de cómputos influye en la dureza de los problemas en línea: ¿podría, por favor, explicar esto?
Oleksandr Bondarenko
bueno, su clase de complejidad típica generalmente se define en términos de algún tipo de recurso vinculado. Mi punto era que los problemas en línea (como -server) son difíciles de una manera que no depende de ningún modelo de complejidad para la máquina subyacente. K
Suresh Venkat
Dado que el recurso limitado (además del tiempo y el espacio clásicos) para los algoritmos en línea es la información sobre la instancia completa de un problema dado, si pudiéramos definir la noción de información para este propósito de una manera rigurosa, entonces podríamos hablar de complejidad clases para problemas en línea?
Oleksandr Bondarenko
1
tú podrías. No sé si esto se ha hecho. ¿Asumo que has revisado el libro de Borodin / El-Yaniv?
Suresh Venkat
1
He revisado el libro de Borodin / El-Yaniv pero no he encontrado ninguna formalización de la noción de información. Sin embargo, hay documentos interesantes sobre la complejidad de los consejos ( scholar.google.com/… ).
Oleksandr Bondarenko
0

Hace poco leí el periódico "Juegos contra la naturaleza" (Papadimitriou, 1985) (aquí está el enlace: http://www.sciencedirect.com/science/article/pii/0022000085900455 ). Específicamente, este documento prueba que la Satisfacción Estocástica (SSAT) es completa para PSPACE. ¿Supongo que el SSAT es un problema en línea? Entonces, ¿este artículo está relacionado con su pregunta?

También estoy bastante interesado en problemas de complejidad para problemas en línea. ¡Podemos discutir!

Chico estúpido
fuente