Według (niezweryfikowanego) rachunku historycznego Kołmogorow uważał, że każdy język w ma złożoność obwodów liniowych. (Zobacz wcześniejsze pytanie Hipoteza Kołmogorowa, że ma obwody o rozmiarach liniowych .) Zauważ, że implikuje .PP\mathsf{P}PPPP≠NPP≠NP\mathsf{P}\neq \mathsf{NP} Jednak...
Myśląc o złożoności testowania izomorfizmu wykresów asymetrycznych (patrz moje powiązane pytanie dotyczące cstheory), przyszło mi do głowy pytanie uzupełniające. Załóżmy, że mamy do wielomianu czasu maszynowego Turinga , który na wejściu generuje wykres G M , n z n...
W obliczeniach kwantowych i informacjach kwantowych Nielsena i Chuanga twierdzą, że wiele algorytmów opartych na kwantowych transformacjach Fouriera opiera się na właściwości niezmienniczości Coseta transformatów Fouriera i sugeruje, że właściwości niezmienniczości innych transformacji mogą dać...
Dawno temu myślałem o tym problemie, ale nie mam o nim pojęcia. Algorytm generujący jest następujący. Zakładamy, że istnieje dyskretnych węzłów ponumerowanych od do . Następnie dla każdego w , nadrzędny ty węzeł w drzewie będzie losowym węzłem w . Iteruj po każdym , aby wynik był losowym drzewem z...
Jaka jest najbardziej znana złożoność obliczenia dokładnej odległości edycji między dwoma ciągami o tej samej długości przy użyciu przestrzeni roboczej, która jest podliniowa w wielkości wejścia? Zakładam, że dane wejściowe są przechowywane w jakimś formacie tylko do odczytu. Czy to wcześniej...
Ostatnio Dana Scott zaproponowała stochastyczny rachunek lambda, próbę wprowadzenia elementów probabilistycznych do (nietypowego) rachunku lambda w oparciu o semantykę zwaną modelem grafowym. Jego slajdy można znaleźć na przykład w Internecie , a jego artykuł w Journal of Applied Logic , t. 12...
Wikipedia wymieniła cztery problemy, które są w ale że są poza : Rozkład na czynniki całkowite; Dyskretny logarytm; Symulacja układów kwantowych; Obliczanie wielomianu Jonesa w pewnych korzeniach jedności.PBQPBQPBQPPPP Czy są jakieś inne takie
Pytanie główne / ogólne Niech LLL będzie językiem. Zdefiniuj języki LiLiL_i pomocą L0=LL0=LL_0 = L i Li={xwy:xy∈Li−1,w∈L}Li={xwy:xy∈Li−1,w∈L}L_i = \{xwy : xy \in L_{i-1}, w \in L\} dla i≥1i≥1i \geq 1 . Rozważmy L = ⋃ l i . Tak więc wielokrotnie „osadzić” L w siebie, aby uzyskać L...
USTCONN to problem, który wymaga podjęcia decyzji, czy istnieje ścieżka od wierzchołka źródłowego sss do wierzchołka docelowego ttt na wykresie GGG , gdzie wszystkie są podane jako część danych wejściowych. Omer Reingold wykazał, że USTCONN znajduje się w L (doi: 10.1145 / 1391289.1391291 ). Dowód...
Obecnie obliczanie liczb rzeczywistych w najpopularniejszych językach jest nadal wykonywane za pomocą operacji zmiennoprzecinkowych. Z drugiej strony, teorie takie jak efektywność typu drugiego (TTE) i teoria domen od dawna obiecują dokładne obliczenie rzeczywistych liczb. Najwyraźniej problem...
W swoim artykule z 1995 r. „ Algorytmy czasowe wielomianowe dla faktoryzacji pierwotnej i logarytmów dyskretnych na komputerze kwantowym” Peter W. Shor omawia ulepszenie części algorytmu faktoryzacji polegającej na ustalaniu kolejności. Standardowe wyjścia algorytm , dzielnik w kolejności R o x...
Chciałbym wygłosić wykład matematyczny na temat systemu kontroli wersji git . Obecnie jest szeroko stosowany w matematyce, a także w branży informatycznej. Na przykład społeczność HoTT (Homotopy Type Theory) korzysta z niego i jest to system do wspólnej edycji plików tekstowych, niezależnie od...
Problem decyzyjny CNF-SAT można opisać następująco: Dane wejściowe: wzór logiczny ϕϕ\phi w spójnej postaci normalnej. Pytanie: Czy istnieje przypisanie zmiennej spełniające ϕϕ\phi ? Rozważam kilka różnych podejść do rozwiązania CNF-SAT za pomocą niedeterministycznej maszyny Turinga z dwiema...
Niech będzie liczbą całkowitą o wartości funkcja taka, że 2 F jest # P . Czy wynika z tego, że F jest w # P ? Czy istnieją powody, by sądzić, że nie zawsze tak będzie? Jakieś referencje, o których powinienem wiedzieć?faFF2 F.2F2F# P#P\#PfaFF# P#P\#P Nieoczekiwanie sytuacja ta pojawiła się (ze...
Poniżej MSO oznacza monadyczną logikę drugiego rzędu grafów z kwantyfikacjami zbioru wierzchołków i zbocza. Niech będzie niewielką zamkniętą rodziną grafów. Z teorii drugorzędnej grafu Robertsona i Seymour wynika, że charakteryzuje się skończoną listą zakazanych nieletnich. Innymi słowy, dla...
Dobrze wiadomo, że problem równoważności jest nierozstrzygalny dla ogólnych języków bezkontekstowych. Jednak wszystkie dowody tego faktu, o których jestem świadomy, wydają się obejmować pewne niejednoznaczne gramatyki bezkontekstowe. Z tego powodu chciałbym zapytać, czy wiadomo, czy problem...
Jestem doktorantem pracującym w dziedzinie informatyki teoretycznej. Przeczytałem artykuły badawcze wielu badaczy i widziałem wiele narzędzi i matematyki, których używają do projektowania algorytmu. Na przykład patrz ten artykuł badawczy [Pierwotność w P] . Nie powiedziałbym, że ten artykuł...
Pierce (2002) wprowadza relację pisania na stronie 92, pisząc: Relacja typowania wyrażeń arytmetycznych, zapisana „t: T”, jest zdefiniowana przez zestaw reguł wnioskowania przypisujących typy do terminów a przypis mówi: Symbol ∈∈\in jest często używany zamiast:. Moje pytanie brzmi po prostu,...
Parzystość-P jest zbiorem języków rozpoznawanych przez niedeterministyczną maszynę Turinga, która może rozróżniać tylko parzystą liczbę lub nieparzystą liczbę ścieżek „akceptacji” (zamiast zerowej lub niezerowej liczby ścieżek akceptacji). Zatem Parity-P jest w zasadzie PP „s karłowate młodsze...
Określić Gaussa złożoność danego matrycy, tak aby minimalna ilość elementarnych wierszy i kolumn operacji wymaganych do matrycy w postaci górnej trójkątnej. Jest to wielkość od do (poprzez eliminację Gaussa). Pojęcie ma sens w każdej dziedzinie.n×nn×nn \times n000n2n2n^2 Ten problem z pewnością...