Powszechnie wiadomo, że i K 3 , 3 są niedozwolone w przypadku wykresów planarnych. Istnieją setki zakazanych nieletnich dla wykresów osadzanych na torusie. Liczba niedozwolonych nieletnich dla wykresów osadzanych na powierzchni rodzaju g jest funkcją wykładniczą g . Moje pytanie...
To pytanie jest podobne do jednego z moich poprzednich pytań. Wiadomo, że jest niedozwolonym pomniejszeniem dla wykresów szerokości co najwyżej .Kt+2Kt+2K_{t+2}ttt Czy istnieje ładnie skonstruowana, sparametryzowana, nieskończona rodzina wykresów (innych niż pełne wykresy i wykresy siatki),...
Biorąc pod uwagę , ile k -DNF z n zmiennymi i klauzulami m jest tautologią? (lub ile k- CNN jest niezadowalających?)m,n,km,n,km, n,
Sieć przełączników (nazwa została wymyślona) składa się z trzech typów węzłów: jeden węzeł początkowy jeden węzeł końcowy jeden lub więcej węzłów Switch Węzeł przełączający ma 3 wyjścia: lewy, górny, prawy; ma dwa stany L i R oraz stan docelowy TL lub TR . Do każdego przełącznika można przejść...
Załóżmy, że graf jest ( , b ) -connected jeśli usunięcie wszelkich ciągu wierzchołków oraz wszelkich b krawędziami z G liści zawsze podłączonego wykresie. Na przykład wykres połączony z k , zgodnie ze standardową definicją, jest połączony ( k - 1 , 0 ) , zgodnie z nową definicją. Czy istnieje...
Kontekst: relacje między logiką a automatami Twierdzenie Büchiego stwierdza, że logika Monadic drugiego rzędu nad łańcuchami (MSO) przechwytuje klasę zwykłych języków. Dowód faktycznie pokazuje, że egzystencjalne MSO ( ∃MSO∃MSO\exists\text{MSO} lub EMSO ) nad łańcuchami wystarczy do...
Załóżmy, że zbudowaliśmy uniwersalny komputer kwantowy. Z wyjątkiem problemów związanych z bezpieczeństwem (kryptografia, prywatność, ...), które z obecnych problemów w świecie rzeczywistym mogą skorzystać z korzystania z niego? Interesują mnie zarówno: problemy obecnie nierozwiązywalne dla...
Szukam algorytmu do połączenia dwóch drzew wyszukiwania binarnego o dowolnej wielkości i zakresie. Oczywisty sposób byłoby przejść o wdrażaniu tego byłoby znaleźć całe poddrzewa, których zakres można dopasować do dowolnego węzła zewnętrznego w drugim drzewie. Jednak najgorszy czas działania tego...
Wiele lat temu słyszałem, że obliczenie minimalnego NFA (niedeterministycznego automatu skończonego) z DFA (deterministycznego) było otwartym pytaniem, w przeciwieństwie do odwrotnego kierunku, który jest znany od dziesięcioleci i jest dobrze zbadany z wydajnym algorytm. Czy ktoś wymyślił...
( tutaj też nie ma odpowiedzi) (d,λ)(d,λ)(d,\lambda)νν\nuU(d)U(d)\mathcal{U}(d)|supp ν|=d|supp ν|=d|\mathrm{supp} \ \nu| =d∥EU∼νU⊗U†−EU∼μHU⊗U†∥∞≤λ‖EU∼νU⊗U†−EU∼μHU⊗U†‖∞≤λ\Vert \mathbb{E}_{U \sim \nu} U \otimes U^{\dagger} - \mathbb{E}_{U \sim \mu_H} U \otimes U^{\dagger}\Vert_{\infty} \leq...
Fraktalny labirynt to labirynt, który zawiera swoje kopie. Np. Następujący Mark Mark Wolf z tego artykułu : Zacznij od MINUS i przejdź do PLUS. Po wprowadzeniu mniejszej kopii labiryntu zapisz jej nazwę literową, ponieważ będziesz musiał pozostawić tę kopię przy wyjściu. Musisz wyjść z każdej...
Obliczenia kwantowe ograniczone w czasie są oczywiście bardzo interesujące. A co z obliczeniami kwantowymi ograniczonymi przestrzenią? Znam wiele interesujących wyników obliczeń kwantowych z sublogarytmicznymi granicami przestrzeni i różnego rodzaju modelami automatów kwantowych. Z drugiej strony...
O ile mi wiadomo, większość implementacji generowania liczb pseudolosowych w praktyce wykorzystuje metody, takie jak rejestry sprzężenia zwrotnego z przesunięciem liniowym (LSFR) lub te algorytmy „Mersenne Twister”. Chociaż zdają wiele (heurystycznych) testów statystycznych, nie ma teoretycznych...
2dca (dwukierunkowe deterministyczne automaty licznikowe) (Petersen, 1994) może rozpoznać następujący jednoargumentowy język: POWER={02n∣n≥0}.POWER={02n∣n≥0}.\begin{equation} \mathtt{POWER} = \lbrace 0^{2^n} \mid n \geq 0 \rbrace. \end{equation} Czy jest jakiś inny nietrywialny, unary język...
Czytam o klasach grafów, dla których izomorfizm grafów ( ) jest . Jednym z takich przypadków są wykresy ograniczonej wartościowości (maksimum nad stopniem każdego wierzchołka), jak wyjaśniono tutaj . Ale uznałem to za zbyt abstrakcyjne. Byłbym wdzięczny, gdyby ktokolwiek mógł zasugerować mi...
Wykresy planarne mają rodzaj zero. Wykresy osadzane na torusie mają co najwyżej rodzaj 1. Moje pytanie jest proste: Czy są jakieś problemy, które można rozwiązać wielomianowo na wykresach planarnych, ale trudne NP na wykresach rodzaju 1? Bardziej ogólnie, czy są jakieś problemy, które można...
Uczyłem dolne granice dzisiaj, a jeden z uczniów zapytał o powód nazwą C . Oficjalne wyjaśnienie jest takie, że „A” oznacza „Alternacja”.AC0AC0AC^0ACACAC Nie pamiętam, jak wiele lat temu powiedziano mi, że Nick Pippenger Steve Cook nazywa się NCNCNC cześć Nicka Pippengera (klasa Nicka), a później...
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...
Wiemy, że programy liniowe (LP) można rozwiązać dokładnie w czasie wielomianowym za pomocą metody elipsoidy lub metody punktu wewnętrznego, takiej jak algorytm Karmarkara. Niektóre LP z super-wielomianową (wykładniczą) liczbą zmiennych / ograniczeń można również rozwiązać w czasie wielomianowym,...
Większość stron, które odwiedziłem czytając ten interesujący temat, podaje coś podobnego „jedynymi potęgami dwóch (innych niż 2), które występują w tej sekwencji, są te z głównym wykładnikiem potęgi” (MathWorld) lub „Po 2 sekwencja ta zawiera następujące potęgi 2: [...], które są...