Złożoność przypadków ogólnych

Złożoność przypadków ogólnych to poddziedzina teorii złożoności obliczeniowej , która bada złożoność problemów obliczeniowych na „większości danych wejściowych”.

Złożoność przypadków ogólnych to sposób pomiaru złożoności problemu obliczeniowego poprzez zaniedbanie małego zestawu niereprezentatywnych danych wejściowych i uwzględnienie najgorszego przypadku złożoności pozostałych. Mały jest zdefiniowany w kategoriach gęstości asymptotycznej. Pozorna skuteczność ogólnej złożoności przypadków polega na tym, że w przypadku szerokiej gamy konkretnych problemów obliczeniowych najtrudniejsze przypadki wydają się rzadkie. Typowe przypadki są stosunkowo łatwe.

Takie podejście do złożoności wywodzi się z kombinatorycznej teorii grup , której tradycja obliczeniowa sięga początku ubiegłego stulecia. Pojęcie złożoności rodzajowej zostało wprowadzone w artykule z 2003 roku, w którym autorzy wykazali, że dla dużej klasy skończenie generowanych grup ogólna złożoność czasowa niektórych klasycznych problemów decyzyjnych z kombinatorycznej teorii grup, a mianowicie problemu słownego , problemu koniugacji i problemu członkostwa, jest liniowy.

Szczegółowe wprowadzenie do ogólnej złożoności przypadków można znaleźć w ankietach.

Podstawowe definicje

Gęstość asymptotyczna

Niech I będzie nieskończonym zbiorem danych wejściowych dla problemu obliczeniowego.

Definicja 1. Funkcja rozmiaru na I jest mapą o nieskończonym zakresie ${\ displaystyle \ sigma: ja \ do \ mathbb {N}} .$ Kula o promieniu n to ${\ Displaystyle B_ {n} = \ {x \ in I \ mid \ sigma (x) \ równoważnik n \}}$ .

Jeśli dane wejściowe są zakodowane jako łańcuchy w skończonym alfabecie, rozmiar może być długością łańcucha.

Niech $} \}}$$n$ będzie zbiorem rozkładów prawdopodobieństwa , gdzie jest rozkładem prawdopodobieństwa na $\ displaystyle B_ { n}}$ . Jeśli kule są skończone, to każda z nich $może$$równoprawdopodobną dystrybucję$ co jest najczęstszym przypadkiem. Zauważ, że tylko skończenie wiele ${\ Displaystyle B_ {n}}$ 's mogą być puste lub mieć ${\ Displaystyle \ mu _ {n} (B_ {n}) = 0}$ ; ignorujemy je.

Definicja 2. Asymptotyczna gęstość podzbioru $wynosi$ ρ $_ {n\to \infty }\mu _{n}(X\cap B_{n})},$ gdy ten limit istnieje.

Gdy kule są skończone i jest miarą równie prawdopodobną, ${n}}$$B_$

${\ Displaystyle \ rho (X) = \ lim {\ Frac {| X \ cap B_ {n} |} {| B_ {n} |}}.}$

$_ }$ użyć zamiast kul i zdefiniuj ${\ Displaystyle \ rho '(X) = \ lim {\ Frac {| X \ cap I_ {n} |} {| I_ {n} |}}}$ . Argument za pomocą Twierdzenie Stolza $,$ istnieje $,$ istnieje przypadku

Definicja jest ogólna, jeśli ${\ Displaystyle \ rho (X) = 1}$$X$ jeśli $0}$${\ Displaystyle \ rho (X)$ . X jest wykładniczo (superpolimianem) ogólnym, jeśli zbieżność do granicy w definicji 2 jest wykładniczo (superwielomianem) szybka itd.

Ogólny podzbiór X jest asymptotycznie duży. To $,$ czy X wydaje się duże w praktyce jak szybko się do 1. Zbieżność superwielomianowa wydaje się

Ogólne klasy złożoności

Definicja 4 Algorytm jest w GenP (ogólnie w czasie wielomianowym), jeśli nigdy nie daje błędnych odpowiedzi i jeśli daje poprawne odpowiedzi w czasie wielomianowym na ogólnym zbiorze danych wejściowych. Problem występuje w GenP , jeśli dopuszcza algorytm w GenP . Podobnie dla GenL (ogólnie czas liniowy ), GenE (ogólnie czas wykładniczy z wykładnikiem liniowym) GenExp (ogólnie czas wykładniczy) itp. ExpGenP jest podklasą GenP , dla której odpowiedni zestaw generyczny jest wykładniczo generyczny.

Bardziej ogólnie dla dowolnego ${\ Displaystyle f: \ mathbb {N} \ do \ mathbb {N}}$ zdefiniować klasę Gen (f) odpowiadającą złożoności czasowej O ( f ) na ogólnym zbiorze danych wejściowych fa .

Definicja 5. Algorytm rozwiązuje problem ogólnie, jeśli nigdy nie daje błędnych odpowiedzi i jeśli daje poprawne odpowiedzi na ogólny zestaw danych wejściowych. Problem jest ogólnie rozwiązywalny, jeśli jest rozwiązany ogólnie przez jakiś algorytm.

Teoria i zastosowania

Problemy kombinatorycznej teorii grup

• Słynne problemy nierozstrzygalne : przy odpowiednich hipotezach problemy związane ze słowem, koniugacją i decyzją o członkostwie są generalnie wielomianowe.
• Problemy wyszukiwania słów i koniugacji są w GenP dla wszystkich ustalonych skończenie przedstawionych grup.

• Dobrze znana procedura wyliczania coset dopuszcza obliczalną górną granicę ogólnego zestawu danych wejściowych.

• Algorytm Whiteheada do testowania, czy jeden element wolnej grupy jest odwzorowywany na inny przez automorfizm, ma górną granicę wykładniczego najgorszego przypadku, ale działa dobrze w praktyce. Pokazano, że algorytm jest w GenL .

• Problem koniugacji w rozszerzeniach HNN może być nierozwiązywalny nawet dla wolnych grup . Jednak ogólnie jest to czas sześcienny.

Problem zatrzymania i problem korespondencji pocztowej

• Problem zatrzymania maszyny Turinga z taśmą jednostronną jest w większości przypadków łatwy do rozstrzygnięcia; jest w GenP

Sytuacja w przypadku taśmy dwustronnej jest nieznana. Istnieje jednak pewnego rodzaju dolna granica dla maszyn obu typów. Problem zatrzymania nie występuje w ExpGenP dla żadnego modelu maszyny Turinga,

• Problem z korespondencją pocztową występuje w ExpGenP .

Arytmetyka Presburgera

Problem decyzyjny dla arytmetyki Presburgera dopuszcza podwójną wykładniczą dolną granicę najgorszego przypadku i potrójną wykładniczą górną granicę najgorszego przypadku. Ogólna złożoność nie jest znana, ale wiadomo, że problem nie występuje w ExpGenP .

NP zupełne problemy

Ponieważ dobrze wiadomo, że problemy NP-zupełne mogą być przeciętnie łatwe, nie jest niespodzianką, że kilka z nich jest również ogólnie łatwych.

• trzech spełnialności występuje w ExpGenP .
• Problem sumy podzbioru występuje w GenP .

Funkcje jednokierunkowe

Istnieje ogólna wersja złożoności funkcji jednokierunkowej , która daje tę samą klasę funkcji, ale pozwala rozważyć inne założenia bezpieczeństwa niż zwykle.

Kryptografia klucza publicznego

Seria artykułów poświęcona jest kryptoanalizie protokołu wymiany kluczy Anshel-Anshel-Goldfeld , którego bezpieczeństwo opiera się na założeniach dotyczących grupy warkoczy . Kulminacją tej serii są prace Miasnikova i Ushakova (2008), w których zastosowano techniki z ogólnej złożoności przypadku, aby uzyskać pełną analizę ataku opartego na długości i warunków, w jakich on działa. Ogólny punkt widzenia sugeruje również rodzaj nowego ataku zwanego atakiem ilorazowym i bezpieczniejszą wersję protokołu Anshel-Anshel-Goldfeld.

Lista ogólnych wyników teoretycznych

• Słynne twierdzenie Rice'a stwierdza $,$ że ​​​​jeśli F podzbiorem zbioru cząstkowych $funkcji$ obliczalnych do to jeśli jego dopełnienie jest puste, problem decydowania, czy dana maszyna Turinga oblicza funkcję w F , jest nierozstrzygalny. Następujące twierdzenie daje wersję ogólną.

Twierdzenie 1 Niech I będzie zbiorem wszystkich maszyn Turinga. Jeśli F jest podzbiorem wszystkich częściowych funkcji obliczalnych od $Displaystyle \ mathbb {N}}$ do samej siebie, tak że F i jej dopełnienie są niepuste, to problem z podjęciem decyzji, czy dana maszyna Turinga, czy nie, N {\ oblicza funkcję z F nie jest rozstrzygalna na żadnym wykładniczym ogólnym podzbiorze I .

• Następujące twierdzenia pochodzą z:

Twierdzenie 2 Zbiór języków formalnych , które są generycznie obliczalne, ma miarę zero.

Twierdzenie 3 Istnieje nieskończona hierarchia ogólnych klas złożoności. Dokładniej dla właściwej funkcji złożoności fa , $\ Displaystyle Gen (f) \ subsetneq Gen (f ^ {3})}$ .

Następne twierdzenie pokazuje, że tak jak istnieją problemy z całkowitym przypadkiem przeciętnym w obrębie problemów NP o dystrybucji, istnieją również problemy z całkowitym przypadkiem ogólnym. Argumenty w przypadku ogólnym są podobne do argumentów w przypadku przeciętnym, a problem zupełnego przypadku ogólnego jest również przeciętny. Jest to problem zatrzymania z ograniczoną dystrybucją.

Twierdzenie 4 Istnieje pojęcie generycznej wielomianowej redukcji czasu, w odniesieniu do której problem zatrzymania z ograniczeniami dystrybucyjnymi jest zupełny w klasie problemów dystrybucyjnych NP.

Porównania z poprzednimi pracami

Czas prawie wielomianowy

Meyer i Paterson definiują algorytm jako czas prawie wielomianowy lub APT, jeśli zatrzymuje się on w krokach p(n) na wszystkich wejściach oprócz p(n) o rozmiarze n . Najwyraźniej algorytmy APT są zawarte w naszej klasie GenP . Widzieliśmy kilka NP zupełnych w GenP , ale Meyer i Paterson pokazują, że tak nie jest w przypadku APT. Dowodzą, że problem NP zupełny jest redukowalny do problemu w APT wtedy i tylko wtedy, gdy P = NP . Zatem APT wydaje się znacznie bardziej restrykcyjny niż GenP .

Złożoność przypadku średniego

Złożoność przypadków ogólnych jest podobna do złożoności przypadków przeciętnych . Istnieją jednak pewne istotne różnice. Ogólna złożoność przypadku jest bezpośrednią miarą wydajności algorytmu na większości danych wejściowych, podczas gdy średnia złożoność przypadku jest miarą równowagi między łatwymi i trudnymi przypadkami. Ponadto złożoność przypadku generycznego w naturalny sposób odnosi się do problemów nierozstrzygalnych .

Załóżmy, że $algorytmem$ , którego złożoność czasowa jest $średniej$ na $Displaystyle T: I \ do \ mathbb {N}}$ \ . Co możemy wywnioskować o zachowaniu na typowych danych wejściowych? ${\ displaystyle {\ mathcal {A}}}$

Przykład 1 $ciągu$ I będzie wszystkich ${\ displaystyle | w |}$ i $zdefiniuj$ jako . Zdefiniuj $n$ zbiór słów o długości i załóż, że $miarą$ jest równie Przypuszczam, że T (w) = n $T (w) = 2 ^ {2 ^ {n}} }$ wszystkich oprócz jednego słowa w każdym i T $Displaystyle$ na słowach wyjątkowych.

W tym przykładzie T jest z pewnością wielomianem na typowych danych wejściowych, ale T nie jest wielomianem średnio. T jest w GenP .

Przykład 2 Trzymaj I i ${\ Displaystyle \ sigma (w) = | w |}$ jak poprzednio, ale zdefiniuj ${\ Displaystyle \ mu (w) = 2 ^ {- 2 | w | -1}}$ i ${\ Displaystyle T (w) = 2 ^ {| w |}}$ . T jest średnio wielomianem, mimo że jest wykładniczy na typowych danych wejściowych. T nie jest w GenP .

W tych dwóch przykładach ogólna złożoność jest ściślej związana z zachowaniem na typowych danych wejściowych niż średnia złożoność przypadku. Średnia złożoność przypadku mierzy coś innego: równowagę między częstotliwością trudnych przypadków a stopniem trudności. Z grubsza mówiąc, algorytm, który jest średnio wielomianowy, może mieć tylko subwielomianowy ułamek danych wejściowych, które wymagają czasu superwielomianowego do obliczenia.

Niemniej jednak w niektórych przypadkach ogólna i przeciętna złożoność przypadków są dość zbliżone do siebie. Funkcja ${\ Displaystyle f: I \ rightarrow \ mathbb {R} ^ {+}}$ jest wielomianem na $kulach$ , jeśli istnieje ${\ displaystyle k \geq 1}$ takie, że ${\ Displaystyle \ suma _ {w \ w I_ {n}} f ^ {1/k} (w) \ mu _ {n} (w) = O (n)}$ gdzie ${\ displaystyle \ {\ mu _ {n} \}}$ to zespół wywołany przez ${\ displaystyle \ mu}$ . Jeśli f $-średnim i dla wielu$ wielomianem na $-średnim$ na sferach, f jest wielomianem na zachodzi odwrotność

Twierdzenie $jest$ Jeśli funkcja jest wielomianem na $,$ sferach f sferyczna gęstość asymptotyczna ${\ Displaystyle \ rho '}$ .

Twierdzenie 6 $, że$$pełny$ algorytm ma subwykładniczy czas ograniczony T a częściowy algorytm dla tego samego problemu jest w ExpGenP w odniesieniu do zespół $} \}}$$n$ odpowiadający miary prawdopodobieństwa na wejściach ja dla $}$ . Następnie istnieje kompletny algorytm, który ma $złożoność$ czasową.

Bezbłędne algorytmy heurystyczne

W artykule z 2006 roku Bogdanov i Trevisan byli bliscy zdefiniowania ogólnej złożoności przypadków. Zamiast algorytmów cząstkowych biorą pod uwagę tzw. bezbłędne algorytmy heurystyczne. Są to kompletne algorytmy, które mogą zawieść, zatrzymując się z wyjściem „?”. Klasa AvgnegP jest zdefiniowana jako składająca się ze wszystkich bezbłędnych algorytmów heurystycznych $A$ , które działają w czasie i dla których prawdopodobieństwo niepowodzenia na pomijalne, tj. Zbiega się superwielomianowo szybko do 0. AvgnegP jest podzbiór GenP . Bezbłędne algorytmy heurystyczne są zasadniczo takie same, jak algorytmy z łagodnymi błędami, zdefiniowane przez Impagliazzo, gdzie algorytmy wielomianowe o średnim czasie są charakteryzowane za pomocą tak zwanych łagodnych schematów algorytmów.