Czy znana jest jakaś klasa złożoności zawierająca internetowe odpowiedniki problemów związanych z optymalizacją?

Czy znana jest jakaś klasa złożoności zawierająca internetowe odpowiedniki problemów związanych z optymalizacją? Jeśli nie, to jak można zdefiniować taką klasę?

Wiemy, że wiele problemów ma swoją wersję online: np. Wersja online problemu pakowania bin. Problemy online są trudniejsze, ponieważ mierzone są ich współczynnikami konkurencyjności.

I nie znalazłem niczego podobnego w zoo złożoności .

Zasadniczo możemy powiedzieć, że nie ma problemów online, ale tylko algorytmy online dla problemów offline. Jeśli jednak występują problemy online, dlaczego nie może zawierać klasy złożoności?

cc.complexity-theory complexity-classes

— Oleksandr Bondarenko
źródło

Czy ma to związek z algorytmami strumieniowymi ( cstheory.stackexchange.com/search?q=stream )?

— MS Dousti,

Algorytmy online nie są tożsame z algorytmami strumieniowymi: w streamingu czynnikiem ograniczającym jest przestrzeń maszyny streamingowej (więc ma ona tylko pamięć krótkotrwałą). W algorytmach internetowych czynnikiem ograniczającym jest brak wiedzy o tym, co się zbliża (więc ma ekstremalną krótkowzroczność)

— Suresh Venkat

@Suresh: Oh, rozumiem. Dziękuję za wyjaśnienie.

— MS Dousti,

Odpowiedzi:

Jednym z trudnych aspektów definiowania klas złożoności dla problemów online jest to, że w zasadzie nie ma ograniczeń co do rodzajów obliczeń, które mogę wykonać po przeczytaniu danych wejściowych. Innymi słowy, problemy online są trudne, nawet jeśli mam (na przykład) wyrocznię NP przetwarzającą dane wejściowe po ich otrzymaniu.

Można sobie wyobrazić, że przy bardziej ograniczonym procesorze, nawet prostsze zadania predykcyjne stają się trudniejsze do wykonania, ale ogólnie trudność w projektowaniu algorytmów online wynika ze zdolności przeciwnika do zmiany danych wejściowych po zbudowaniu modelu prognostycznego.

— Suresh Venkat
źródło

Jak brak limitu rodzajów obliczeń wpływa na trudność problemów online: czy mógłbyś to wyjaśnić?

— Oleksandr Bondarenko

K

$K$

Ponieważ ograniczonym zasobem (oprócz klasycznego czasu i przestrzeni) dla algorytmów online jest informacja o kompletnym wystąpieniu danego problemu, gdybyśmy mogli rygorystycznie zdefiniować pojęcie informacji w tym celu, to czy moglibyśmy mówić o złożoności zajęcia z problemów online?

— Oleksandr Bondarenko

mógłbyś. Nie wiem, czy zostało to zrobione. Zakładam, że sprawdziłeś książkę Borodin / El-Yaniv?

— Suresh Venkat,

Przejrzałem książkę Borodin / El-Yaniv, ale nie znalazłem żadnej formalizacji pojęcia informacji. Istnieją jednak interesujące artykuły na temat złożoności porad ( scholar.google.com/… ).

— Oleksandr Bondarenko

Niedawno przeczytałem artykuł „Gry przeciwko naturze” (Papadimitriou, 1985) (tutaj jest link: http://www.sciencedirect.com/science/article/pii/0022000085900455 ). W szczególności ten dokument dowodzi, że Stochastic Satisfiable (SSAT) jest kompletny z PSPACE. Myślę, że SSAT jest problemem online? Czyli ten artykuł jest w jakiś sposób związany z twoim pytaniem?

Interesują mnie również problemy ze złożonością problemów online. Możemy porozmawiać!

— Głupi facet
źródło