Niech będzie jakimś językiem, a następnie zdefiniujemy spójność syntaktyczną jako u ∼ v : ⇔ ∀ x , y ∈ X ∗ : x u y ∈ L ↔ x v y ∈ L i iloraz monoidu X ∗ / ∼ L wynosi nazywany składniowym monoid z L .L ⊆ X∗L⊆X∗L \subseteq X^{\ast}u ∼ v : ⇔ ∀ x , y∈ X∗: x u y∈ L ↔ x v y∈ L.u∼v:⇔∀x,y∈X∗:xuy∈L↔xvy∈L u...
Pytanie. W swoim artykule Ulepszona symulacja obwodów stabilizatora , Aaronson i Gottesman twierdzą, że symulacja obwodu CNOT jest zakończona w ⊕L (przy zmniejszeniu przestrzeni logarytmicznej). Oczywiste jest, że jest on zawarty w ⊕L ; jak zachowuje się wynik twardości? Równoważnie: czy...
Rozważmy wektor zmiennych i zestaw wiązań liniowych określonych przez A → x ≤ b .x⃗ x→\vec{x}Ax⃗ ≤bAx→≤bA\vec{x}\leq b Ponadto rozważ dwa
Czy istnieje , język NP lub P-zupełny, który ma pewną rodzinę grup symetrii G n (lub groupoid , ale wtedy pytania algorytmiczne stają się bardziej otwarte) działając (w czasie wielomianowym) na zbiorach L n = { l ∈ L ∣ | l | = n } tak, że jest kilka orbit, tj. taki, że | L n / G n | < n c dla...
Robin Milner zdefiniował bigraphy jako rodzaj struktury graficznej o strukturze podobnej do wykresu, ale w której węzły można zagnieżdżać. Uogólniają kalkulatory procesowe, takie jak CCS i calculus, ale wydaje się, że Milner zamierzał je stosować znacznie bardziej ogólnie: notatki z seminarium na...
Wiele kryptosystemów z kluczem publicznym ma pewnego rodzaju sprawdzalne zabezpieczenia. Na przykład kryptosystem Rabin jest tak samo trudny jak faktoring. Zastanawiam się, czy istnieje taki rodzaj możliwego do udowodnienia bezpieczeństwa dla kryptosystemów tajnych kluczy, takich jak AES. Jeśli...
Co wiadomo o klasie języków rozpoznawanych przez automaty skończone posiadające ten sam stan początkowy i akceptacji? Jest to właściwy podzbiór zwykłych języków (ponieważ każdy taki język zawiera pusty ciąg znaków), ale jak bardzo jest słaby? Czy istnieje prosta charakterystyka algebraiczna? To...
Biorąc pod uwagę macierzy A z racjonalnym pozycji. Jaką złożoność sprawdzenia A można diagonalizować?n×nn×nn\times nAAAAAA Podejrzewam, że można to zrobić w P, ale nie znam żadnego odniesienia. Bardziej interesujące jest jednak pytanie, czy istnieje jakaś lepsza klasa złożoności, aby uchwycić ten...
ppp≤d≤d\le dbias(p)≜|Prx∈{0,1}n(p(x)=0)−Prx∈{0,1}n(p(x)=1)|>ϵbias(p)≜|Prx∈{0,1}n(p(x)=0)−Prx∈{0,1}n(p(x)=1)|>ϵbias(p) \triangleq |\Pr_{x\in\{0,1\}^n}(p(x)=0)-\Pr_{x\in\{0,1\}^n}(p(x)=1)| \gt \epsilon * Gdy piszę losowy wielomian o stopniu ≤d≤d\le d a n zmiennych, można myśleć o każdy...
Mam problem algebraiczny związany z wektorami w dziedzinie GF (2). Niech będą wektorami wymiaru , a . Znaleźć wielomianowej algorytm czasową znajdzie (0,1)-wektor tego samego wymiaru tak, że nie jest sumą każdy wektory między . Dodawanie wektorów odbywa się ponad polem GF (2), które ma dwa elementy...
Niech kwadratowa rzeczywista macierz A i dwa wektory x i b o długości n , takie, że A x = b . Rozwiązanie x poprzez standardową eliminację Gaussa daje łączną złożoność prawie O ( n 3 ) . Są jednak przypadki, w których rozwiązywanie (lub ϵ - rozwiązywanie w przybliżeniu) dla x kosztuje O ( n log ρ...
Jak trudno jest znaleźć najrzadsze rozwiązanie układu równań liniowych? Bardziej formalnie, rozważ następujący problem decyzyjny: Instancja: układ równań liniowych o współczynnikach całkowitych i liczbie ccc . Pytanie: Czy istnieje rozwiązanie dla systemu z co najmniej ccc zmiennymi przypisanymi...
Szukałem mnożenia macierzy, więc najpierw odwiedziłem algorytmy mnożenia macierzy wiki. W referencjach znalazłem artykuł, który twierdzi, że używa algorytmu O ( n2)l o g( n ) )O(n2)losol(n))O(n^2 log(n)) , chciałbym przeczytać artykuł, ale jest skomplikowany i zajmie zbyt wiele czasu, aby go...
Moje doświadczenie dotyczy teorii / logiki złożoności (gdzie przez większość czasu jest tylko jeden proces) oraz przetwarzania rozproszonego (gdzie jest procesów, a jeden lub więcej może zawieść z czasem). Jednak chcę teraz móc powiedzieć coś o procesie odradzania / tworzenia / wydzielania innego...
Wiemy np. Z Koutis-Miller-Peng (na podstawie pracy Spielmana i Tenga), że możemy bardzo szybko rozwiązać układy liniowe dla macierzy które są wykresem macierzy Laplaciana dla niektórych rzadkich wykresów z nieujemnymi wagami krawędzi .Ax=bAx=bA x = bAAA Teraz (pierwsze pytanie) rozważ użycie...
Szukam listy o znanej lub nieznanej złożoności różnych problemów teoretycznych / algebraicznych. Na przykład, GCD w jest otwarty,N.do1NC1NC^1 faktoring w jest otwarty,P.PP obliczanie kohomologii snopów to -hard# P#P\#P , Arora i Barak stwierdzają, że wariant faktoringu jest -Complete (choć nie...
Załóżmy, że chcemy pomnożyć macierzy. Algorytm powolnego mnożenia macierzy działa w czasie O ( n 3 ) i wykorzystuje pamięć O ( n 2 ) . Najszybsze mnożenie macierzy przebiega w czasie n ω + o ( 1 ) , gdzie ω jest stałą algebry liniowej, ale co wiadomo o jej złożoności pamięci?n×nn×nn \times...
Na cs.stackexchange zapytałem o bibliotekę algebird scala na githubie, spekulując, dlaczego mogą potrzebować abstrakcyjnego pakietu algebry. Strona github zawiera kilka wskazówek: Implementacje Monoidów dla interesujących algorytmów aproksymacyjnych, takich jak filtr Bloom, HyperLogLog i...
Niech prawdziwa macierz k×nk×nk\times n ( k≤nk≤nk\le n ) AA{\bf A} z tą właściwością, że dowolny zbiór kkk kolumn ma pełną rangę. P: istnieje efektywny sposób deterministyczny znaleźć wektor tak że zmodyfikowanym matrycy ' = [aa{\bf a}A′=[Aa]A′=[Aa]{\bf A}' = [{\bf A}\;{\bf a}] zachowuje tę samą...
EDYCJA (autor: Tara B): Nadal byłbym zainteresowany odniesieniem do dowodu na to, ponieważ musiałem to udowodnić na własne potrzeby. Szukam dowodu Twierdzenia 4, który pojawia się w tym artykule: Nieskończona hierarchia skrzyżowań języków bezkontekstowych autorstwa Liu i Weinera. Twierdzenie...