Biorąc pod uwagę ukierunkowany wykres z n węzłami, tak że każdy wierzchołek ma dokładnie dwie krawędzie wychodzące, a liczbę naturalną N zakodowaną dwójkowo, dwa wierzchołki s i t, Chcę policzyć liczbę (niekoniecznie prostych) ścieżek od s do t w obrębie N kroków. Czy to trudny problem # P? Lub...
Wiadomo, że dolna granica ogólnego przeciwnika charakteryzuje złożoność kwantowych zapytań z powodu przełomowej pracy Reichardta i in. Ta sama linia pracy ustanawia również połączenia ze strukturą programu zakresu do projektowania algorytmów kwantowych. Wiele interesujących algorytmów kwantowych,...
Jeśli otrzymamy dwa ciągi o rozmiarze n1n1n_1 i , standardowe obliczanie odległości edycji Levenshteina odbywa się za pomocą algorytmu dynamicznego o złożoności czasowej i złożoności przestrzennej . (Niektóre ulepszenia można wprowadzić w zależności od odległości edycji , ale nie zakładamy, że jest...
Podjęto próby zaatakowania problemu izomorfizmu grafów za pomocą kwantowego losowego chodzenia twardych rdzeni (symetryczne, ale bez podwójnego zajęcia). Symetryczna moc matrycy przylegania, która wydawała się obiecująca, wykazano jako niekompletne ogólnych wykresów na tym papierze Amir Rahnamai...
ETH stwierdza, że SAT nie może być rozwiązany w najgorszym przypadku w czasie podwykonawczym. Co z przeciętną sprawą? Czy istnieją naturalne problemy związane z NP, które są przypuszczalnie trudne w przeciętnym przypadku? Średni przypadek oznacza średni czas pracy z równomiernym rozkładem na...
Napraw problem wyszukiwania NP-complete, np. Formularz wyszukiwania SAT. Wyszukiwanie Levin zapewnia algorytm do rozwiązywania który jest w pewnym sensie optymalny. Konkretnie, algorytm jest „Wykonanie wszystkich możliwych programów w zazębianie na wejściowego , gdy niektórzy powraca odpowiedzieć...
jest powszechnie przypuszczane, że jest fałszywe.R P= NP.RP.=N.P.RP = NP Ale wyobraź sobie przez chwilę, że to prawda. W takim przypadku, jakie jest prawdopodobieństwo, że ?P.= NP.P.=N.P.P = NP Innymi słowy: w świecie, w którym , co może być nadal postrzegane jako przeszkoda dla nas, aby wierzyć...
Twierdzenie dychotomii Schaefera pokazuje, że każdy problem CSP powyżej można rozwiązać w czasie wielomianowym lub jest on NP-kompletny. Dotyczy to tylko problemów CSP o ograniczonej szerokości, z wyłączeniem na przykład SAT i Horn-SAT. Ogólne problemy CSP o nieograniczonej szerokości mogą być...
Szukam wyników twardości na kolorowanie wierzchołków wykresów z ograniczonym stopniem. Biorąc pod uwagę wykres , wiemy, że dla dowolnego ϵ > 0 trudno jest oszacować χ ( G ) przy współczynniku | V | 1 - ϵ, chyba że NP = ZPP [ 1 ]. Ale co, jeśli maksymalny stopień G jest ograniczony przez d ?...
Sudoku jest dobrze znaną łamigłówką, która jest kompletna NP. Sudoku Binarne to wariant, który dopuszcza tylko cyfry i 1 . Zasady są następujące.000111 Każdy wiersz i każda kolumna musi zawierać równą liczbę zer i jedynek. Każdy wiersz i każda kolumna jest unikalny. Żaden wiersz ani kolumna nie...
Zdefiniuj jako klasę języków, które mogą być akceptowane przez (wielopasmową) maszynę Turinga w czasie f ( n ) + 1 . („ + 1 ” ma jedynie na celu uproszczenie notacji i uniknięcie pomyłek.) Zauważ, że nie ma O ( ⋅ ) wokół f ( n ) + 1 .D T I M E (f( n ) )DTIME(f(n))\mathsf{DTIME}(f(n))fa( n ) +...
Wygładzona analiza była stosowana wiele razy, aby zrozumieć czas działania dokładnych algorytmów dla wielu problemów, takich jak programowanie liniowe i k-średnich. Istnieją dość ogólne wyniki w tej dziedzinie, na przykład Heiko Röglin i Berthold Vöcking, Analiza wygładzania programowania liczb...
Jaki jest związek między i ? Innymi słowy, czy problemy, które dopuszczają wyszukiwanie lokalne w czasie wielomianowym, są przybliżone? Czy problemy z optymalizacją w przybliżeniu sugerują ogólnie lokalny algorytm wyszukiwania?P L SPLS\mathsf{PLS}A P
Biorąc pod uwagę deterministyczną grę z sumą zerową z częściową informacją i tylko skończoną liczbą stanów, których możliwymi rezultatami są odpowiednio [przegrana, remis, wygrana] o wartościach odpowiednio [-1,0, + 1], jaka jest złożoność przybliżenia wartości takich gra w dodatku...
Czy wiemy, że hierarchia się nie zwija ( dla wszystkich d )?TC0TC0\mathsf{TC^0}TC0d⊊TC0d+1TCd0⊊TCd+10\mathsf{TC^0_d} \subsetneq \mathsf{TC^0_{d+1}}ddd Wpis do zoo dla TC0TC0\mathsf{TC^0} wspomina tylko o separacji między głębokością 2 i 3. Czy istnieje również standardowe odniesienie do faktu, że...
To pytanie jest motywowane tym postem. Czy potrafisz określić sumę dwóch permutacji w czasie wielomianowym? oraz moje zainteresowanie obliczeniowymi właściwościami permutacji. Sekwencja różnic permutacji π liczb 1 , 2 , … n + 1 jest tworzona przez znalezienie różnicy między każdą dwiema sąsiednimi...
Automaty szczątkowego stanu skończonego (RFSA, zdefiniowane w [DLT02]) to NFA, które mają kilka fajnych cech wspólnych z DFA. W szczególności zawsze istnieje kanoniczny minimalny rozmiar RFSA dla każdego zwykłego języka, a język rozpoznawany przez każdy stan w RFSA jest resztkowy, podobnie jak w...
Zawarte w między każdym poziomie hierarchii wielomianowej złożoności są różne klasy, w tym , DP , BH k oraz Σ P I ∩ Õ P ja . Z powodu braku lepszej terminologii będę odwoływał się do tych i innych klas pośrednich między poziomami i i i + 1 w hierarchii wielomianowej. Dla celów tego pytania,...
Niedawno zacząłem dużo czytać o złożoności dowodów i bardzo podobało mi się to, co czytałem. Naprawdę chciałbym dowiedzieć się więcej na ten temat, ale mam trudności ze znalezieniem dobrego materiału dla początkujących. Czy ktoś mógłby polecić jakieś
Próbuję zrozumieć, do której klasy złożoności należy następujący problem: Wykładniczy wielomianowy problem z korzeniem (EPRP) Niech będzie wielomianem o deg ( p ) ≥ 0 ze współczynnikami wyciągniętymi z pola skończonego G F ( q ) z q liczbą pierwszą, a r pierwotnym pierwiastkiem dla tego pola....