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
źródło
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.
źródło
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ć!
źródło