Ist eine Komplexitätsklasse bekannt, die Online-Gegenstücke zu Optimierungsproblemen enthält?

10

Ist eine Komplexitätsklasse bekannt, die Online-Gegenstücke zu Optimierungsproblemen enthält? Wenn nicht, wie kann eine solche Klasse definiert werden?

Wir wissen, dass viele Probleme ihre Online-Version haben: zB Online-Version des Papierverpackungsproblems. Die Online-Probleme sind schwieriger, gemessen an ihren Wettbewerbsverhältnissen.

Und ich habe im Komplexitätszoo nichts Ähnliches gefunden .

Grundsätzlich kann man sagen, dass es keine Online-Probleme gibt, sondern nur Online-Algorithmen für Offline-Probleme. Wenn es jedoch Online-Probleme gibt, warum kann es keine Komplexitätsklasse geben, die diese enthält?

cc.complexity-theory complexity-classes Oleksandr Bondarenko
quelle
Bezieht sich dies auf Stream- Algorithmen ( cstheory.stackexchange.com/search?q=stream )?
MS Dousti
1
Online-Algorithmen sind nicht dasselbe wie Stream-Algorithmen: Beim Streaming ist der begrenzende Faktor der Platz der Streaming-Maschine (sie hat also nur ein Kurzzeitgedächtnis). In Online-Algorithmen ist der begrenzende Faktor mangelndes Wissen darüber, was kommt (so hat es extreme Myopie)
Suresh Venkat
@ Suresh: Oh, ich verstehe. Danke für die Klarstellung.
MS Dousti

Antworten:

4

Ein schwieriger Aspekt beim Definieren von Komplexitätsklassen für Online-Probleme besteht darin, dass die Art der Berechnungen, die ich nach dem Lesen der Eingabe ausführen kann, im Prinzip unbegrenzt ist. Mit anderen Worten, Online-Probleme sind schwierig, selbst wenn ich (zum Beispiel) ein NP-Orakel habe, das die Eingabe verarbeitet, sobald sie eintrifft.

Es ist denkbar, dass mit einem eingeschränkteren Prozessor noch einfachere Vorhersageaufgaben schwieriger auszuführen sind. Im Allgemeinen ergibt sich die Schwierigkeit beim Entwerfen von Online-Algorithmen jedoch aus der Fähigkeit des Gegners, die Eingabe zu ändern, nachdem Sie ein Vorhersagemodell erstellt haben.

Suresh Venkat
quelle
Wie keine Begrenzung der Arten von Berechnungen die Härte von Online-Problemen beeinflusst: Können Sie dies bitte erklären?
Oleksandr Bondarenko
K
Da die begrenzte Ressource (zusätzlich zu klassischer Zeit und Raum) für Online-Algorithmen die Information über die vollständige Instanz eines bestimmten Problems ist, könnten wir über Komplexität sprechen, wenn wir den Begriff der Information für diesen Zweck streng definieren könnten Klassen für Online-Probleme?
Oleksandr Bondarenko
1
du könntest. Mir ist nicht bekannt, ob dies getan wurde. Ich nehme an, Sie haben das Borodin / El-Yaniv-Buch überprüft?
Suresh Venkat
1
Ich habe das Buch Borodin / El-Yaniv durchgesehen, aber keine Formalisierung des Begriffs Information gefunden. Es gibt jedoch interessante Artikel zur Komplexität von Ratschlägen ( Scholar.google.com/… ).
Oleksandr Bondarenko
0

Ich habe kürzlich die Zeitung "Spiele gegen die Natur" (Papadimitriou, 1985) gelesen (hier ist der Link: http://www.sciencedirect.com/science/article/pii/0022000085900455 ). Insbesondere beweist dieses Papier, dass die stochastische Erfüllbarkeit (SSAT) PSPACE-vollständig ist. Ich denke, die SSAT ist ein Online-Problem? Also hat dieses Papier etwas mit Ihrer Frage zu tun?

Ich interessiere mich auch sehr für Komplexitätsprobleme bei Online-Problemen. Wir können diskutieren!

Dummer Typ
quelle