Известен ли какой-либо класс сложности, содержащий онлайн-аналоги задач оптимизации?

10

Известен ли какой-либо класс сложности, содержащий онлайн-аналоги задач оптимизации? Если нет, то как можно определить такой класс?

Мы знаем, что у многих проблем есть онлайн-версия: например, онлайн-версия проблемы с упаковкой бункера. Проблемы онлайн сложнее, если судить по их конкурентоспособности.

И я не нашел ничего похожего по сложности в зоопарке .

По сути, мы могли бы сказать, что в сети нет проблем, а есть только онлайн-алгоритмы для работы в автономном режиме. Однако, если есть проблемы в сети, почему не может быть класса сложности, содержащего их?

cc.complexity-theory complexity-classes Александр бондаренко
источник
Это связано с потоковыми ( cstheory.stackexchange.com/search?q=stream ) алгоритмами?
MS Dousti
1
Оперативные алгоритмы - это не то же самое, что потоковые алгоритмы: при потоковой передаче ограничивающим фактором является пространство потоковой машины (поэтому она имеет только кратковременную память). В онлайн-алгоритмах ограничивающим фактором является незнание того, что грядет (поэтому у него сильная близорукость)
Суреш Венкат
@ Суреш: О, я вижу. Благодарю за разъяснение.
MS Dousti

Ответы:

4

Один сложный аспект определения классов сложности для онлайн-задач заключается в том, что в принципе нет ограничений на то, какие вычисления я могу выполнять после прочтения ввода. Другими словами, онлайн проблемы являются сложными, даже если у меня есть (например) оракул NP, обрабатывающий ввод после его поступления.

Можно предположить, что с более ограниченным процессором труднее выполнять даже более простые задачи прогнозирования, но в целом сложность разработки онлайновых алгоритмов связана со способностью противника изменять входные данные после построения модели прогнозирования.

Суреш Венкат
источник
Как отсутствие ограничений на виды вычислений влияет на сложность онлайн-задач: не могли бы вы объяснить это?
Александр Бондаренко
К
Поскольку ограниченный ресурс (в дополнение к классическому времени и пространству) для онлайн-алгоритмов является информацией о полном экземпляре данной проблемы, если бы мы могли строго определить понятие информации для этой цели, то могли бы мы говорить о сложности занятия по онлайн проблемам?
Александр Бондаренко
1
вы могли бы. Я не знаю, было ли это сделано. Я полагаю, вы проверили книгу Бородина / Эль-Янива?
Суреш Венкат
1
Я просмотрел книгу Бородина / Эль-Янива, но не нашел формализации понятия информации. Тем не менее, есть интересные статьи о сложности советов ( scholar.google.com/… ).
Александр Бондаренко
0

Недавно я прочитал газету «Игры против природы» (Пападимитриу, 1985) (вот ссылка: http://www.sciencedirect.com/science/article/pii/0022000085900455 ). В частности, эта статья доказывает, что стохастическая удовлетворенность (SSAT) является PSPACE-полной. Я думаю, что SSAT - это проблема в сети? Таким образом, эта статья несколько связана с вашим вопросом?

Я также весьма заинтересован в проблемах сложности для онлайн-проблем. Мы можем обсудить!

Тупой парень
источник