Myślę, że tego nie rozumiem, ale konwersja wygląda na mnie jako konwersja β , która nic nie robi, szczególny przypadek konwersji β, w której wynikiem jest tylko termin z abstrakcji lambda, ponieważ nie ma nic do zrobienia, rodzaj bezcelowej konwersji β .ηη\etaββ\betaββ\betaββ\beta Może więc...
Istnieje wiele algorytmów, które mogą analizować gramatykę bezkontekstową w czasie . Używając mnożenia macierzy, można nawet iść asymptotycznie szybciej.O(n3)O(n3)O(n^3) Jednak wszystkie algorytmy do analizy dowolnych CFG, które znam, mają najgorsze wykorzystanie przestrzeni (chociaż, co prawda,...
Większość operacji głosowania pojawia się dość często w tolerancji na uszkodzenia (i bez wątpienia w innych miejscach), gdzie funkcja generuje bit równy, która zawsze pojawia się najczęściej w wartości bitów wejściowych. Dla uproszczenia załóżmy, że ilekroć wejście zawiera taką samą liczbę bitów w...
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...
Czy automatyczne dowodzenie twierdzeń i przeszukiwanie dowodów jest łatwiejsze w liniowych i innych zdaniach logiki strukturalnej pozbawionej kurczenia? Gdzie mogę przeczytać więcej o automatycznym dowodzeniu twierdzeń w tych logikach i roli skurczu w poszukiwaniu
Czy są jakieś algorytmy rozwiązywania SAT, które nie są oparte na DPLL? Czy wszystkie algorytmy używane przez solwery SAT są oparte na
Powszechnie wiadomo, że komputery kwantowe są silniejsze niż ich klasyczne odpowiedniki pod względem złożoności zapytań . Czy istnieją inne modele (naturalne lub sztuczne), które są ściśle kwantowe i klasyczne pod względem złożoności zapytań? Separacja może być włączona specyficzne...
W latach 90. widzę wiele badań nad hiper-obliczeniami , ale w ostatnich latach wydaje się, że niewiele jest pracy na ten temat. Czy to prawda, że badania w tej dziedzinie wygasły? Jeśli tak, jakie mogą być tego przyczyny? Czy ten obszar przekonująco okazał się mało...
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...
Myślę, że dobrym pomysłem byłoby sporządzenie listy twierdzeń stwierdzających, że P nie jest równe NP wtedy i tylko wtedy, gdy takie i takie wyjścia, pewna klasa złożoności jest zawarta w innej klasie złożoności i tak dalej.
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...
Pracuję nad zestawem problemów dla klasy i pomyślałem o pytaniu związanym z tym, nad czym pracowałem. Czy istnieje minimalna liczba stanów, które musi mieć automat skończony, aby zaakceptować ciągi binarne reprezentujące liczby podzielne przez liczbę całkowitą n? We wcześniejszym zestawie problemów...
Rozglądałem się daleko za takimi aplikacjami i najczęściej okazało się, że są krótkie. Potrafię znaleźć wiele zastosowań topologii i podobnych struktur na zestawach policzalnych (lub niepoliczalnych), ale rzadko znajduję zbiory niepoliczalne jako przedmiot badań przez informatyków, a zatem prowadzi...
Jakie są znane skuteczne algorytmy do obliczania wyznacznikiem macierzy współczynników całkowitą o ZmZm\mathbb{Z}_m , pierścień reszt modulo mmm . Liczba mmm może nie być liczbą pierwszą, lecz złożoną (więc obliczenia są wykonywane w pierścieniu, a nie w polu). O ile mi wiadomo (czytaj poniżej),...
Czy podjęto prace nad tym, jak złożoność przypadkowych instancji # 2-SAT zmienia się w zależności od gęstości klauzuli? To znaczy: w jaki sposób trudność liczenia satysfakcjonujących rozwiązań dla losowo generowanej instancji 2-SAT różni się w zależności od gęstości klauzuli? W szczególności, czy...
Załóżmy, że jest drzewem o stałym stopniu, którego struktury nie znamy. Problem polega na wyprowadzeniu drzewa T przez zadawanie zapytań o postać: „Czy węzeł x leży na ścieżce od węzła a do węzła b ?”. Załóżmy, że na każde zapytanie można odpowiedzieć w stałym czasie przez wyrocznię. Znamy wartość...
Jak wiadomo, istnieje wiele anomolii w maszynach Turinga z pojedynczą taśmą, gdy czas jest o(n2)o(n2)o(n^2) : symulacja wielopasmowa TM, symulacja większego alfabetu taśmy za pomocą tylko {0,1,b}{0,1,b}\{0,1,b\} , konstruowania czasu, nieszczelności twierdzenia o hierarchii czasu, ... Również...
Złożoność zoo nie ma wiele o . Szukam ładnego problemu z który jest na wyższych poziomach hierarchii, tj. Problemu w ale nie wiadomo, że jest w .SCSC\mathsf{SC} † D T i m e S p a c e ( n O ( 1 ) , lg O ( 1 ) n) D T i m e S p a c e ( n O ( 1 ) , lg 2
Na sercu jestem fizykiem, więc myślę, że One-Way Quantum Computing jest genialny. W szczególności obliczenia kwantowe oparte na pomiarach stanu graficznego (MBQC) stanowiły bardzo udany rozwój badań nad obliczeniami kwantowymi, których autorami są Raussendorf & Briegel . Trzeba tylko...
Mafia to popularna gra fabularna na imprezach, szczegółowy opis jest dostępny na stronie wikipedia http://en.wikipedia.org/wiki/Mafia_%28game%29 . Zasadniczo działa w następujący sposób: Na początku każdemu z graczy potajemnie przypisywana jest rola, dostosowana do mafii lub miasta. Każda rola...