Klasy złożoności związane z listowaniem wszystkich rozwiązań?

Czytałem pytanie na Stack Overflow, pytając, czy to NP- twarde, aby wymienić wszystkie proste cykle na wykresie zawierającym określony węzeł i przyszło mi do głowy, że nie mogę wymyślić żadnej istniejącej klasy złożoności, która byłaby odpowiednia dla mówiąc o problemach z formularzem „wymień wszystkie rozwiązania tego problemu”. Klasa NP w pewnym sensie składa się z problemów, które pytają, czy istnieje co najmniej jedno rozwiązanie, klasa FNP prosi o utworzenie jednego rozwiązania, a klasa #P prosi o policzenie, ile jest rozwiązań, ale żadne z nich nie dotyczy złożoności wyczerpującego wyliczenia wszystkich możliwych rozwiązań.

Czy istnieje klasa złożoności do opisywania problemów, które mają postać „biorąc pod uwagę predykat obliczany w czasie wielomianowym i ciąg , wylicz wszystkie dla których jest prawdziwe, z zastrzeżeniem [wstaw niektóre odpowiednie ograniczenia złożoności]? ” Rozumiem, że ustalenie ograniczeń może być trudne, biorąc pod uwagę, że liczba rozwiązań może być wykładniczo większa niż wielkość wejściowego , choć nie wydaje się to niemożliwe. $P(x, y)$ $x$ $y$ $P(x, y)$ $x$

— templatetypedef
źródło

Ciekawy. Być może w praktyce zbyt wiele przypadków istotnych problemów często ma wykładniczą liczbę rozwiązań, o ile występują. Instancje dla SAT i CLIQUE mają ogólnie dużą przestrzeń do rozwiązania.

— chi

Oto kolejny ansatz na sformalizowanie tego. Problem jest (X-wyliczalnych) jeśli istnieje X algorytm z tak, że Zwraca th rozwiązania (to znaczy p o ) wrt niektórych zamawianie. Zauważ, że jest to podobne do tego, jak czasami definiuje się RE. To omija wielkość przestrzeni rozwiązania i koncentruje się na tym, jak trudno jest znaleźć następne rozwiązanie. Oczywiście całkowity koszt jest dostępny poprzez zsumowanie.

P

$P$

X E

$XE$

A

$A$

A (x, i)

$A(x,i)$

i

$i$

I

$I$

y

$y$

P (x, y)

$P(x,y)$

— Raphael

(Nigdy nie widziałem go zdefiniować jako klasy , ale jesteś świadomy koncepcji wyliczenia wielomianu z opóźnieniem ?)

@Raphael To może nie być to, czego szukamy. Na przykład, jeśli najlepszy algorytm dla musi iterować wszystkie rozwiązania, dopóki nie znajdzie i uruchomi się w czasie , wówczas złożoność, której szukamy, to , ale suma sugerowałaby złożoność .

A (x, i)

$A(x,i)$

i

$i$

Θ (f (| x |))

$\Theta(f(|x|))$

Θ (f (| x |))

$\Theta(f(|x|))$

Θ (f (| x |)^{2})

$\Theta(f(|x|)^2)$

— Lieuwe Vinkhuijzen,

@RickyDemer To właśnie trząsłam się z rękawów, prawda? Dobrze wiedzieć, że istnieje ustalona formalizacja.

— Raphael

Pojęcie, którego szukasz, nazywa się złożonością wyliczania , czyli badaniem złożoności obliczeniowej wyliczania (wymieniania) wszystkich rozwiązań problemu (lub członków języka / zestawu). Algorytmy wyliczania można modelować jako proces dwuetapowy: etap wstępnego obliczania i faza wyliczania z opóźnieniem . Oba te etapy mają swoją złożoność czasu i przestrzeni (być może również entropię). W ogólnym duchu złożoności często występują między nimi kompromisy.

Etap wstępnego obliczenia wykonuje pewną pracę, która jest konieczna przed wyliczeniem pierwszego rozwiązania. Może to obejmować znalezienie samego rozwiązania lub zainicjowanie jakiejś dużej struktury danych, która zmniejszy ogólne opóźnienie między poszczególnymi rozwiązaniami.

Opóźnienie to koszty związane z zasobami do obliczenia niezbędnego pomiędzy dowolnymi wyliczonych rozwiązań. Innymi słowy, opóźnienie jest miarą przestrzeni i czasu potrzebnego do wytworzenia rozwiązania po . Mówi się, że problemy, których rozwiązania wymagające czasu dla każdego wyliczenia mają stałe opóźnienie. Wymóg czas mówi się, że wielomian opóźnienia. $i+1^{th}$ $i^{th}$ $O(1)$ $O(poly(n))$

W przypadku problemu z wyliczeniem, o którym konkretnie wspomniałeś w swoim pytaniu, powinieneś przyjrzeć się klasie i jej pokrewnemu rodzeństwu w sekcji 2.1 „Wyliczenia: algorytmy i złożoność” Johannesa Schmidta (Link na dole). $ENUM_{NP}$

Dlaczego zależy nam na czasie i opóźnieniu wstępnego obliczenia?

Opóźnienie jest bardzo kluczowe dla zrozumienia prawdziwych zawiłości problemów z wyliczaniem. Wyliczenie elementów (do rozmiaru ) i gdzie jest wzorem boolowskim (tj. SAT), zajmuje czas wykładniczy. Jednak wyliczanie przez $\Sigma^*$ $n$ $\{ \vec{x} : \phi(\vec{x}) \}$ $\phi(\vec{x})$ $\Sigma*$ wymaga tylko ciągłego opóźnienia, ponieważ możesz po prostu przejść przez elementy w określonej kolejności. Z tego, co wiemy, opóźnienie wyliczenia rozwiązań dla instancji 3SAT może być wykładnicze. Naszym zadaniem jako teoretyków złożoności jest uchwycenie, dlaczego ten drugi problem jest zasadniczo trudniejszy (bardziej złożony) niż poprzedni. Opóźnienie robi całkiem niezłą robotę, pokazując tę różnicę.

Podobnie musimy również wiedzieć, ile wykonano wstępnego obliczenia. Możemy zmniejszyć opóźnienie dowolnego problemu z wyliczaniem do stałego czasu i przestrzeni, wstępnie obliczając wszystkie rozwiązania i przechowując je na liście, która zostanie wyliczona w późniejszym czasie. Wyzwanie polega na znalezieniu najlepszej równowagi między tymi dwoma zasobami.

Kolejność wyliczania elementów może również wpływać na złożoność. Wymaganie zwrotu wyników w określonej kolejności sortowania może wymagać od nas wykonania dodatkowych obliczeń w obu etapach. Chociaż z pewnością badane są również sytuacje, w których wystarcza dowolna kolejność (o ile każdy wyliczony element jest unikalny).

O ile mi wiadomo, klasy te zwykle nie mają zwięzłych etykiet (podobnych do i ). Nie możemy oczekiwać, że będziemy w stanie to zrobić, ponieważ klasy złożoności wyliczeń żonglują wokół 3 lub więcej zasobów (obliczenia wstępne / całkowity czas, przestrzeń, opóźnienie i entropia). Po prostu jest zbyt wiele kombinacji granic zasobów, aby można było podać specjalne nazwy. Nie czyni to tych klas mniej interesującymi, a także nie powstrzymuje badaczy przed próbowaniem. $P$ $NP$

Zasoby

Ta ankieta (naprawdę próba sformalizowania) powinna pomóc Ci zacząć. Dowodzi to również pewnych podstawowych twierdzeń hierarchicznych.

Wyliczenie: algorytmy i złożoność (Johannes Schmidt, 2009)

https://www.thi.uni-hannover.de/fileadmin/forschung/arbeiten/schmidt-da.pdf

Aby uzyskać wyliczenie wyników w złożoności wyliczenia, sprawdź tę kompilację, której kuratorem jest Kunihiro Wasa. Ponieważ jest on podzielony na kategorie według rodzaju problemu, można łatwo znaleźć wiele artykułów poświęconych wyliczaniu cykli graficznych. Powinna być łatwa modyfikacja algorytmów, aby uwzględniały tylko cykle z danym węzłem.

http://www-ikn.ist.hokudai.ac.jp/~wasa/enumeration_complexity.html

— mdxn
źródło

Σ^{*}

$\Sigma^*$

n

$n$

O (1)

$O(1)$

O (1)

$O(1)$

@j_random_hacker Nie sądzę, że twoje myślenie jest złe, choć prawdziwa odpowiedź na twoje pytanie brzmi „to zależy”. Autorzy tych artykułów zwykle wskazują, jakiego modelu obliczeń (zwykła taśma TM vs. RAM vs. Word RAM) używają. Ten wybór zmieni to, co można uznać za operację o stałym czasie, a co nie (takie jak zwiększenie liczby lub generowanie wyniku). Zakłada się, że różnica ta zniknie, gdy tylko opóźnienie stanie się wielomianowe z powodu rozszerzonej tezy Kościoła Turinga.

— mdxn