Pytania otagowane jako cc.complexity-theory

P a NP i inne obliczenia ograniczone do zasobów.

3
Jak trudna jest dokładna symulacja algorytmów i powiązana z nią operacja na klasach złożoności
Zwiastun Ponieważ problem jest długotrwały, tutaj jest szczególny przypadek, który oddaje jego istotę. Problem: Niech A będzie algorytmem detrministycznym dla 3-SAT. Czy problem polega na całkowitej symulacji algorytmu A (na każdym wystąpieniu problemu). P-Space trudne? (Dokładniej, czy istnieją powody, by sądzić, że to zadanie jest trudne dla P-Space, robi coś …
2
Teoria kategorii, złożoność obliczeniowa i połączenia kombinatoryczne?
Próbowałem przeczytać „ Perły projektowania algorytmu funkcjonalnego ”, a następnie „ Algebra programowania ”, i istnieje oczywista zgodność między rekurencyjnie (i wielomianowo) zdefiniowanymi typami danych i obiektami kombinatorycznymi, mającymi tę samą definicję rekurencyjną, a następnie prowadzącą do tych samych formalnych szeregów mocy (lub funkcji generujących), jak pokazano we wstępach do …
3
Wydajne algorytmy przestrzeni logów
Łatwo zauważyć, że każdy problem, który można rozstrzygnąć w deterministycznej przestrzeni logicznej ( ), pojawia się co najwyżej w czasie wielomianowym ( P ). Wiele znanych algorytmów przestrzeni logicznej (na przykład: nieukierowana łączność st, izomorfizm płaskiego wykresu) działa w O ( n k ), gdzie k jest niesamowicie duże.L.L.LP.P.PO ( …
4
Złożoność znalezienia drugiego rozwiązania przy poprawnym rozwiązaniu problemu NP-zupełnego
Chcę dowiedzieć się, czy istnieją jakieś ogólne wyniki lub przykłady dotyczące kompletności NP problemu znalezienia drugiego rozwiązania problemu NP-zupełnego. Dokładniej, jestem zainteresowany wszelkimi problemami następującej formy: Biorąc pod uwagę rozwiązanie na przykład I z NP-pełnej problemem jest to, że roztwór S ' ≠ S do I ?SSSIjaIS′≠SS′≠SS' \neq SIII Docenione …
1
Struktura instancji patologicznych dla algorytmów simpleks
O ile rozumiem, wszyscy znają deterministyczne reguły przestawne dla algorytmów simpleksowych mają określone dane wejściowe, na których algorytm wymaga czasu wykładniczego (lub przynajmniej nie wielomianowego), aby znaleźć optymalne. Nazwijmy te przypadki „patologicznymi”, ponieważ zwykle (tj. Na większości danych wejściowych) algorytm simpleks kończy się szybko. Pamiętam z mojego kursu programowania matematycznego, …
2
Twardość sparametryzowanego CLIQUE?
Niech 0≤p≤10≤p≤10\le p\le 1 i rozważmy problem decyzyjny Klika P Wejście: całkowita s , wykres G z T wierzchołki krawędzie Pytanie: sposób zawierać klika na co najmniej wierzchołki?pp_p sssGGGtttGs⌈p(t2)⌉⌈p(t2)⌉\lceil p\binom{t}{2} \rceil GGGsss Instancja CLIQUE zawiera proporcję spośród wszystkich możliwych krawędzi. Wyraźnie CLIQUE jest łatwy dla niektórych wartości . CLIQUE zawiera …
2
MIP z wydajnymi dowodami
Powszechnie wiadomo, że zestawem języków posiadających dwuczłonowy interaktywny system proof, w którym weryfikator działa w czasie wielomianowym (MIP), jest NEXP. Ale czy znane są granice mocy takich interaktywnych dowodów, gdy dowody mają ograniczoną moc? Na przykład, jaka jest klasa języków, które dopuszczają dowody interaktywne z dwoma dowodami z dowodami czasu …
4
Alternatywne pojęcie złożoności oparte na luce między brutalną siłą a najlepszym algorytmem?
Zwykle wydajne algorytmy mają wielomianowe środowisko wykonawcze i wykładniczo dużą przestrzeń rozwiązania. Oznacza to, że problem musi być łatwy w dwóch aspektach: po pierwsze, problem można rozwiązać w wielomianowej liczbie kroków, a po drugie, przestrzeń rozwiązania musi być bardzo ustrukturyzowana, ponieważ środowisko wykonawcze jest tylko polilogarytmiczne pod względem liczby możliwych …
2
Problem cięcia bez H
Załóżmy, że otrzymałeś połączony, prosty, niekierowany wykres H. Problem cięcia bez H jest zdefiniowany następująco: Biorąc pod uwagę prosty, nieukierowany wykres G, istnieje cięcie (podział wierzchołków na dwa niepuste zbiory, L, R), tak że oba wykresy indukowane przez zestawy cięcia (L i R) nie zawierają izomorficznego subgrafu do H . …
2
Czy
W „ostatnim akapicie” „pierwszej strony” następującego artykułu: Vikraman Arvind , Johannes Köbler , Uwe Schöning , Rainer Schuler , „Jeśli NP ma obwody wielomianowe, wówczas MA = AM”, Theoretical Computer Science, 1995. Napotkałem nieco sprzeczne z intuicją twierdzenie: (ΣP2∩ΠP2)NP=ΣP3∩ΠP3(Σ2P∩Π2P)NP=Σ3P∩Π3P(\Sigma^P_2 \cap \Pi^P_2)^{NP} = \Sigma^P_3 \cap \Pi^P_3 Myślę, że powyższa tożsamość została …
1
Czy BPP vs. P to prawdziwy problem po tym, jak wiemy, że BPP leży w P / poly?
My wiemy (teraz około 40 lat, dzięki Adleman, Bennet Gill), że włączenie BPP ⊆⊆\subseteq P / poly, i jeszcze silniejszy BPP / poli ⊆⊆\subseteq P / poli trzymaj. „/ Poly” oznacza, że ​​pracujemy nierównomiernie (osobny obwód dla każdej długości wejściowej nnn ), podczas gdy P bez tego „/ poly” oznacza, …
Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.