Interesuje mnie, czy istnieją jakieś dobre artykuły ekspozycyjne lub ankiety, do których mogę się odnieść, pisząc o operatorach klas złożoności : operatorach, które przekształcają klasy złożoności, np. Dodając do nich kwantyfikatory. Przykłady operatorów Poniższe można interpretować jako absolutną minimalną listę operatorów, którą odpowiedź powinna umieć opisać. Tutaj jest dowolnym zestawem …
Osłona krawędzi jest podzbiorem krawędzi wykresu, tak że każdy wierzchołek wykresu sąsiaduje z co najmniej jedną krawędzią okładki. Poniższe dwa artykuły mówią, że liczenie krawędzi jest zakończone #P : Prosty FPTAS do zliczania krawędzi i generowania krawędzi krawędzi wykresów ścieżek . Jednakże, chyba że coś przeoczyłem, nie zawierają one odniesienia …
Twierdzenia o hierarchii są podstawowymi narzędziami. Wiele z nich zebrano we wcześniejszym pytaniu (patrz Jakie hierarchie i / lub twierdzenia dotyczące hierarchii znasz? ). Niektóre separacje klas złożoności wynikają bezpośrednio z twierdzeń hierarchicznych. Przykłady takich dobrze znanych separacji: L ≠ PS.P.A C.miL≠PSPACEL\neq PSPACE , , , .N P ≠ N …
Kiedy patrzymy na książkę, teoria typów homotopii - widzimy następujące tematy: Homotopy type theory 2.1 Types are higher groupoids 2.2 Functions are functors 2.3 Type families are fibrations 2.4 Homotopies and equivalences 2.5 The higher groupoid structure of type formers 2.6 Cartesian product types 2.7 S-types 2.8 The unit type …
Szukam problemów, które są znane jako NPC dla grafów kierowanych, ale mają algorytm wielomianowy dla grafów bezkierunkowych. Widziałem pytanie dotyczące odwrotnych problemów, które są łatwiejsze niż ich „niekierowany” wariant , ale szukam twardości po stronie ukierunkowanej. Na przykład, zestaw krawędzi sprzężenia zwrotnego jest znany jako NPC na ukierunkowanych, ale wielomianowych …
Jednoznaczne automaty skończone (UFA) są specjalnym typem niedeterministycznych automatów skończonych (NFA). NFA jest nazywany jednoznacznym, jeśli każde słowo ma co najwyżej jedną ścieżkę akceptującą.w ∈ Σ∗w∈Σ∗w\in \Sigma^* Oznacza to, .D F.A ⊂ UfaA ⊂ NfaZArefaZA⊂UfaZA⊂N.faZADFA\subset UFA\subset NFA Znane powiązane wyniki automatów: Minimalizacja NFA jest kompletna z PSPACE. Minimalizacja NFA w …
Gowers przedstawił ostatnio problem, który nazywa „dyskretną determinacją Borela”, którego rozwiązanie dotyczy dolnych granic obwodu dowodzenia. Czy możesz podać podsumowanie podejścia, które jest dostosowane do grupy teoretyków złożoności? Co potrzeba, aby to podejście wykazało cokolwiek , w tym ponowne udowodnienie znanych dolnych granic?
Jest tylko bardzo mało informacji na temat kompletnego NP rozwiązania problemu liniowego równania diofantyny w liczbach całkowitych nieujemnych. To znaczy, czy jest to rozwiązanie w nieujemne x1,x2,...,xnx1,x2,...,xnx_1,x_2, ... , x_n do równania , gdzie wszystkie stałe są dodatnie? Jedyną godną uwagi wzmianką o tym problemie, który znam, jest Teoria programowania …
W pracy „Efficient Al Algorytm for Graph Isomorphism” autorstwa Corneila i Gotlieba, 1970, stwierdzono hipotezę, na której opierał się algorytm rozwiązywania GI w czasie wielomianowym. Mianowicie: że reprezentatywne wykresy wykazują podział automorfizmu na dany wykres Oczywiście, ta hipoteza nie została do tej pory udowodniona (w przeciwnym razie wiedzielibyśmy, że GI …
Zaproponowano mi nauczenie nowatorskiego programu szkoły średniej TCS, który wymaga opracowania programu nauczania. Bardzo chciałbym usłyszeć opinie i sugestie dotyczące tego. Po pierwsze, czy ktoś wie o szkołach średnich, w których program TCS był nauczany z powodzeniem (lub bez powodzenia)? Chodzi o 3-letni program (10-12 klas, w wieku 16-18 lat), …
To pytanie jest prawdopodobnie na granicy między tematem i nie na temat, jednak widziałem tutaj podobne pytania, dlatego zadam to pytanie. Ja realizacji Unikalny kkk -sat solver, którego wejście jest kkk wzór -cnf o co najwyżej 111 spełniająca zadania. Aby przetestować jego praktyczne zachowanie, potrzebuję zestawu takich formuł. Szukałem ich …
Każdy płaski odpowiednio outerplanar wykres spełnia , odpowiednio | E ′ | ≤ 2 | V ′ | - 3 dla każdego podgrafu G ' = ( V ' , E ' ) z G . Również (zewnętrzne) wykresy płaskie można rozpoznać w czasie wielomianowym.G=(V,E)G=(V,E)G=(V,E)|E′|≤3|V′|−6|E′|≤3|V′|−6|E'|\le 3|V'|-6|E′|≤2|V′|−3|E′|≤2|V′|−3|E'|\le 2|V'|-3G′=(V′,E′)G′=(V′,E′)G'=(V',E')GGG Co wiadomo na …
Ukazał się nowy artykuł, w którym twierdzono, że quasi-wielomianowy algorytm jest logarytmem dyskretnym. http://arxiv.org/abs/1306.4244 Jeśli jest poprawny, czy oznacza to, że nie mamy już wykładniczej separacji złożoności klasycznego algorytmu i jego wersji kwantowej dla problemu logarytmu dyskretnego? Czy ma to jakiś wpływ na teorię złożoności kwantowej?
Zastanawiam się, czy są jakieś dokumenty lub badania dotyczące widocznych automatów przesuwających w dół, ale pozwalające na wypychanie słów zamiast pojedynczych liter na stos. Alternatywnie, konstrukcja umożliwiająca wypychanie symboli na -transitions może osiągnąć ten sam cel.ϵϵ\epsilon Oczywiście, takie warianty mogą być tworzone, ale zastanawiam się, czy to rujnuje właściwości zamknięcia …
Używamy plików cookie i innych technologii śledzenia w celu poprawy komfortu przeglądania naszej witryny, aby wyświetlać spersonalizowane treści i ukierunkowane reklamy, analizować ruch w naszej witrynie, i zrozumieć, skąd pochodzą nasi goście.
Kontynuując, wyrażasz zgodę na korzystanie z plików cookie i innych technologii śledzenia oraz potwierdzasz, że masz co najmniej 16 lat lub zgodę rodzica lub opiekuna.