Pytania otagowane jako cc.complexity-theory

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

2
Porównanie dwóch algorytmów dla problemu 3SUM w stosunku do liczb całkowitych
Artykuł „Algorytmy subkwadratowe dla 3SUM” autorstwa Ilyi Baran, Erika D. Demaine'a, Mihai Patrascu ma następującą złożoność 3SUM problemów: otrzymuje listę L.L.L z liczb całkowitych czy istnieją taki sposób, żennnx , y, z∈ L.x,y,z∈L.x,y,z \in Lx + y= z.x+y=z.x+y=z. Twierdzą oni, „W przypadku standardowego tekstu z pamięci RAM bitowych słów, otrzymujemy …
2
Klasy wykresów, w których problemy cyklu Hamiltoniana i ścieżki Hamiltoniana mają różną złożoność
Podczas przeszukiwania Systemu informacji o klasach grafów i ich inkluzjach znalazłem kilka klas grafów, dla których problem cyklu Hamiltoniana jest NP-kompletny, natomiast złożoność problemów ścieżki Hamiltonian NIE jest znana. Niektóre z tych klas to dwuczęściowe wykresy o maksymalnym stopniu 3, wykresy o maksymalnym stopniu 3 i 2 połączone sześcienne wykresy …
2
Problem z izomorfizmem grafów
Robię przegląd literatury na temat problemu izomorfizmu grafów. Większość artykułów, które czytam, są napisane przez EM Luksa i Laszlo Babai. W tych pracach wykorzystano znajomość teorii grup i teorii złożoności na wysokim poziomie. Ponieważ jestem nowy w tej dziedzinie, wiele rzeczy nie jest dla mnie oczywistych. Czy ktoś może mi …
3
W jakiej klasie są algorytmy losowe, które mają błąd z dokładnie 25% szansą?
Załóżmy, że rozważam następujący wariant BPP, który pozwala nam nazywać się E (xact) BPP: Język jest w EBPP, jeśli istnieje wielomianowy losowy czas TG, który akceptuje każde słowo z prawdopodobieństwem dokładnie 3/4 i każde słowo nie w język z prawdopodobieństwem dokładnie 1/4. Oczywiście EBPP jest zawarty w BPP, ale czy …
5
Dlaczego ekonomiści powinni dbać o złożoność obliczeniową
Czy próbując przekonać ekonomistów o znaczeniu teorii złożoności w druku, istnieje standardowe odniesienie do cytowania? Znam post na blogu Noama Nisana , ankietę Tima Roughgarden i rozdział 11 eseju Scotta Aaronsona . Te posty są dostępne dla informatyków, ale nie używają języka ekonomistów i nie są publikowane w miejscach zwykle …
1
Złożoność problemu pokrycia interwałów
Rozważmy następujący problemQQQ : Otrzymujemy liczbę całkowitą i przedziałów z . także liczb całkowitych . Zadanie polega na wybraniu minimalnej liczby przedziałównnnkkk[li,ri][li,ri][l_i,r_i]1≤li≤ri≤2n1≤li≤ri≤2n1\leq l_i\leq r_i\leq 2n2n2n2nd1,…,d2n≥0d1,…,d2n≥0d_1,…,d_{2n}\geq 0 , że dla każdego i = 1 , ... , 2 n , co najmniej d ı odstępach zawierających całkowitą i są zaznaczone.[li,ri][li,ri][l_i,r_i]i=1,…,2ni=1,…,2ni=1,…,2ndidid_iiii Nietrudno …
1
Złożoność próbkowania (w przybliżeniu) transformaty Fouriera funkcji boolowskiej
Jedną rzeczą, którą komputery kwantowe mogą zrobić (być może nawet z tylko BPP + obwody kwantowe głębokości logarytmicznej), jest przybliżenie próbki transformaty Fouriera funkcji logicznej wartościowej w P.±1±1\pm 1 Tutaj i poniżej, kiedy mówię o próbkowaniu transformaty Fouriera, mam na myśli wybranie x zgodnie z . (Znormalizowane w razie potrzeby …
1
Jaka jest złożoność tego problemu kolorowania krawędzi?
Ostatnio spotkałem następujący wariant kolorowania krawędzi. Biorąc pod uwagę połączony niekierowany wykres, znajdź kolorystykę krawędzi, która wykorzystuje maksymalną liczbę kolorów, jednocześnie spełniając ograniczenie, że dla każdego wierzchołka krawędzie padające na v używają co najwyżej dwóch kolorów.vvvvvv Po pierwsze sądzę, że problem jest trudny do rozwiązania. Klasyczne twarde proofy NP na …
3
Konstruktywnie wydajne algorytmy bez sprawdzania poprawności i wydajności
Szukam naturalnych przykładów wydajnych algorytmów (tj. W czasie wielomianowym) ul ich poprawność i skuteczność można konstruktywnie udowodnić (np. w lub ), alePRAPRAPRAHAHAHA nie jest znany żaden dowód wykorzystujący tylko wydajne koncepcje (tzn. nie wiemy, jak udowodnić ich poprawność i wydajność w lub ).TV0TV0TV^0S12S21S^1_2 Mogę samodzielnie tworzyć sztuczne przykłady. Chcę jednak …
2
Status w dolnych granicach obwodu dla obwodów głębokości ograniczonych przez polilog
Złożoność obwodu złożoności jest jednym z głównych obszarów badań w ramach teorii złożoności obwodu. Ten temat ma swoje początki w wynikach takich jak „funkcja parzystości nie jest w ” i „funkcja mod nie jest obliczana przez ”, gdzie jest klasą języków rozstrzygalnych na podstawie niejednolitej, stałej głębokości, wielomianu, nieograniczonego wachlarza …
1
Jakie są podrodziny # P-complete z # 2-SAT?
Krótka wersja. Oryginalny dowód, że # 2-SAT jest #P- kompletny, pokazuje w rzeczywistości, że te przypadki # 2-SAT, które są zarówno monotoniczne (nie obejmujące negacji żadnych zmiennych), jak i dwustronne (wykres utworzony przez klauzule nad zmienne to wykres dwustronny) są # P-twarde . Zatem dwa specjalne przypadki # 2-MONOTONE-SAT i …
2
Czy naprawdę można wykazać silną twardość NP za pomocą zwykłych redukcji czasu politytime?
Niedawno przeczytałem dowód, który miał wykazać, że problem był silnie NP-trudny, po prostu redukując go (w czasie wielomianowym) z problemu silnie NP-trudnego. To nie miało dla mnie żadnego sensu. Pomyślałbym, że musisz pokazać, że wszelkie liczby użyte w redukcji i przypadki problemu, do którego redukujesz, są wielomianowo ograniczone w wielkości …
1
Wykorzystanie dodatkowej mocy metody negatywnego przeciwnika
Negatywna metoda przeciwnika ( A D V±ZAreV.±ADV^\pm ) to SDP, który charakteryzuje złożoność kwantowych zapytań. Jest to uogólnienie powszechnie stosowanej metody przeciwnika ( ) i pokonuje dwie bariery, które utrudniały metodę przeciwnika:A D VZAreV.ADV Bariera testowania właściwości: jeśli wszystkie wystąpienia 0 są daleko od wszystkich 1 wystąpień, wówczas metoda przeciwnika …
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.