Pytania otagowane jako cc.complexity-theory

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

3
Najkrótsza równoważna formuła CNF
Niech będzie zadowalającą formułą CNF z zmiennymi i klauzulami . Niech będzie przestrzenią rozwiązań .F1F1F_1m S F 1 F 1nnnmmmSF1SF1S_{F_1}F1F1F_1 Rozważ problem z określeniem, biorąc pod uwagę , innej formuły CNF z tym samym zestawem zmiennych co , z (ta sama przestrzeń rozwiązania co ), ale z możliwie jak najmniejszą …
3
Dokładne rozwiązywanie superstrun
Co wiadomo o dokładnej złożoności najkrótszego problemu superstrun? Czy można to rozwiązać szybciej niż O∗(2n)O∗(2n)O^*(2^n) ? Czy znane są algorytmy, które rozwiązują najkrótszy superstrun bez redukcji do TSP? UPD: O∗(⋅)O∗(⋅)O^*(\cdot) tłumi czynniki wielomianowe. Najkrótszy problem superstrun to problem, którego odpowiedzią jest najkrótszy ciąg, który zawiera każdy ciąg z danego zestawu …
2
Zastosowania XORification
XORification to technika utrudniania funkcji lub formuły boolowskiej poprzez zastąpienie każdej zmiennej XOR k ≥ 2 odrębnych zmiennych x 1 ⊕ … ⊕ x k . xxxk≥2k≥2k\geq 2x1⊕…⊕xkx1⊕…⊕xkx_1 \oplus \ldots \oplus x_k Zdaję sobie sprawę z zastosowania tej techniki w złożoności dowodu, głównie w celu uzyskania niższych granic przestrzeni dla …
3
Wymień czas i złożoność zapytań
Praca bezpośrednio ze złożonością czasu lub dolnymi granicami obwodu jest przerażająca. Dlatego opracowujemy narzędzia takie jak złożoność zapytań (lub złożoność drzewa decyzyjnego), aby uzyskać kontrolę nad dolnymi granicami. Ponieważ każde zapytanie zajmuje co najmniej jeden krok jednostkowy, a obliczenia między zapytaniami są liczone jako wolne, złożoność czasu jest co najmniej …
1
Najbardziej wydajny sposób na konwersję obwodu na obwód (dowolnej głębokości) za pomocą fanout 1 bramki
EDYCJA (22 sierpnia 2011 r.): Jeszcze bardziej upraszczam pytanie i wyróżniam je. Być może to prostsze pytanie będzie miało łatwą odpowiedź. Przekreślę także wszystkie części pierwotnego pytania, które nie są już istotne. (Podziękowania dla Stasysa Jukny i Ryana O'Donnella za częściową odpowiedź na oryginalne pytanie!) Tło: Biorąc pod uwagę obwód …
4
Czy testy mogą wykazać brak błędów?
(n+1)(n+1)(n + 1) punkty są wymagane do jednoznacznego określenia wielomianu stopnia ; na przykład dwa punkty na płaszczyźnie określają dokładnie jedną linię.nnn Ile punktów jest wymaganych do jednoznacznego określenia funkcji obliczeniowej , biorąc pod uwagę długość programu, który oblicza w ustalonym języku? (tj. związany ze złożonością Kołmogorowa ).f:N→Nf:N→Nf : N …
4
Bezpośrednia redukcja SAT do 3-SAT
Tutaj celem jest zredukowanie arbitralnego problemu SAT do 3-SAT w czasie wielomianowym przy użyciu jak najmniejszej liczby klauzul i zmiennych. Moje pytanie jest motywowane ciekawością. Mniej formalnie chciałbym wiedzieć: „Jaka jest„ najbardziej naturalna ”redukcja z SAT na 3-SAT?” Teraz zmniejszenie, które zawsze widziałem w podręcznikach, wygląda mniej więcej tak: Najpierw …
5
Dlaczego P = NP nie oznacza P = AP (tj. P = PSPACE)?
Powszechnie wiadomo, że jeśli wówczas hierarchia wielomianowa upadnie, a .P=NPP=NP\mathbf{P}=\mathbf{NP}P=PHP=PH\mathbf{P}=\mathbf{PH} Można to łatwo zrozumieć indukcyjnie za pomocą maszyn Oracle. Pytanie brzmi - dlaczego nie możemy kontynuować procesu indukcyjnego poza stałym poziomem naprzemienności i udowodnić (aka )?P=AltTime(nO(1))P=AltTime(nO(1))\mathbf{P}=\mathbf{AltTime}(n^{O(1)})AP=PSPACEAP=PSPACE\mathbf{AP}=\mathbf{PSPACE} Szukam intuicyjnej odpowiedzi.
2
Twierdzenie o hierarchii wielkości obwodu
Myślę, że twierdzenie o hierarchii wielkości dla złożoności obwodów może być dużym przełomem w tej dziedzinie. Czy to ciekawe podejście do separacji klasowej? Motywem tego pytania jest to, że musimy powiedzieć istnieje pewna funkcja, której nie można obliczyć na podstawie obwodów wielkości f(n)f(n)f(n) i można ją obliczyć na podstawie obwodu …
2
Czy istnieje twierdzenie Hierarchia czasu dla PH?
Czy to prawda, że ​​w hierarchii wielomianowej występują problemy, które można rozwiązać w czasie O(nk)O(nk)O(n^k) (przez naprzemienną maszynę Turinga na pewnym poziomie hierarchii wielomianowej), których nie można rozwiązać w O(nk−1)O(nk−1)O(n^{k-1}) na żadnym poziomie hierarchia wielomianowa? Innymi słowy - czy istnieje twierdzenie o hierarchii czasu dla hierarchii wielomianowej, tak jak ma …
4
Zastosowania teorii złożoności
Teoria złożoności wydaje się uchwycić coś fundamentalnego w strukturze wszechświata, ponieważ formalizuje intuicyjne przekonanie, że niektóre problemy są trudniejsze niż inne. Scott Aaronson przewidział : „Założenie o twardości NP będzie w końcu postrzegane jako analogiczne do drugiej zasady termodynamiki lub niemożności sygnalizacji nadświetlnej”. Tak zwane „trudne problemy” są podstawą współczesnej …
1
Czy dominujący problem z zestawem jest ograniczony do płaskich dwustronnych grafów o maksymalnym stopniu NP-3?
Czy ktoś wie o wyniku NP-kompletności dla problemu ZESTAW DOMINUJĄCY na wykresach, ograniczonego do klasy płaskich dwustronnych grafów o maksymalnym stopniu 3? Wiem, że jest NP-kompletny dla klasy grafów płaskich o maksymalnym stopniu 3 (patrz książka Gareya i Johnsona), a także dla grafów dwustronnych o maksymalnym stopniu 3 (patrz M. …
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.