Dana Angluin ( 1987 ; pdf ) definiuje model uczenia się z zapytaniami o członkostwo i teoriami (kontrprzykłady do proponowanej funkcji). Pokazuje, że zwykły język reprezentowany przez minimalny DFA z stanów jest możliwy do nauczenia się w czasie wielomianowym (gdzie proponowane funkcje to DFA) z...
Bezpośrednie twierdzenie o produkcie, nieformalnie, mówi, że obliczenie instancji funkcji f jest trudniejsze niż jednorazowe obliczenie f .kkkfafffaff Typowe bezpośrednie twierdzenia o produktach (np. XOR Lemma Yao) patrzą na złożoność średnich przypadków i twierdzą (bardzo z grubsza), że nie może...
W artykule na temat relatywizacji obliczeń przestrzeni logicznej Ladner i Lynch konstruują wyrocznię, do której . W literaturze można znaleźć więcej patologicznych przykładów. Czytałem kilka artykułów na temat relatywizowanych małych klas kosmicznych, a jednym z podstawowych narzędzi w tym obszarze...
Jakie są twierdzenia dotyczące hierarchii głębokości obwodu? Oświadczenia takie jak jeśli i f ( n ) ∈ n O ( 1 ), to S i z e D e p t h ( n O ( 1 ) , g ( n ) ) ⊊ S i z e D e p t h ( n O (g(n)∈o(f(n))g(n)∈o(f(n))g(n) \in o(f(n))f(n)∈nO(1)f(n)∈nO(1)f(n) \in
W teorii złożoności definicja złożoności czasu i przestrzeni odnosi się do uniwersalnej maszyny Turinga: odpowiednio. liczba kroków przed zatrzymaniem i liczba dotkniętych komórek na taśmie. Biorąc pod uwagę tezę Kościoła-Turinga, powinno być możliwe zdefiniowanie złożoności również pod względem...
Interesuje mnie klasyczny problem REGULARNE WŁĄCZENIE JĘZYKA. Biorąc pod uwagę wyrażenie regularne , oznaczamy przez L ( E ) powiązany z nim język regularny. (Wyrażenia regularne są na stałej alfabetu Ď z unii operacji, Kleene-gwiazdkowe i konkatenacji).miEEL ( E)L(E)L(E)ΣΣ\Sigma Dane wejściowe:...
Mam kilka pytań dotyczących oszukiwania obwodów o stałej głębokości. Wiadomo, że -wise niezależności konieczne oszukać A C 0 obwody głębokości D , gdzie n jest wielkości wejściowych. Jak można to udowodnić?logO ( d)( n )logO(d)(n)\log^{O(d)}(n)A C.0AC0AC^0reddnnn Ponieważ powyższe jest...
Próbuję zrozumieć związek między złożonością algorytmiczną a złożonością obwodów determinant i mnożenia macierzy. Wiadomo, że wyznacznik macierzy można obliczyć w czasie , gdzie to minimalny czas wymagany do pomnożenia dowolnych dwóch macierzy. Wiadomo również, że najlepszą złożonością obwodów...
Szukam wydajnego algorytmu dla problemu: Wejście : dodatnia liczba całkowita 3)n3n3^n (zapisana w bitach) dla jakiejś liczby całkowitej n ≥ 0n≥0n \geq 0 . Wyjście : liczba nnn . Pytanie : Czy możemy obliczyć nnn na podstawie bitów 3)n3)n3^n w czasie O ( n )O(n)O(n) ? To jest teoretyczne...
W przypadku wielomianowego problemu wyszukiwania lokalnego wiemy, że musi istnieć co najmniej jedno rozwiązanie (lokalne optimum). Jednak może istnieć wiele innych rozwiązań, jak trudno jest policzyć liczbę rozwiązań problemu z kompletnym PLS? Jestem szczególnie zainteresowany w problemu...
Czytam słynny artykuł Impagliazzo i Wigdersona w 1997 roku. Ponieważ jestem nowy w tej dziedzinie, a artykuł jest zwięzłą wersją konferencji, mam trudności z podążeniem za nimi. W szczególności niektórym z ich nowych twierdzeń brakuje dowodów. Według mojej najlepszej wiedzy nie opublikowano wersji...
Czy znasz problemy, które są twarde W [1], nawet w przypadku wykresów o ograniczonym stopniu? Wymiar metryczny jest trudny na wykresach ze stopniem co najwyżej 3, ale ma twardość W [2]. Czerwono-niebieski Nonblocker był twardy W [1] na wykresach ze stopniem ograniczonym, ale wystąpił błąd w...
O ile mi wiadomo, dolna granica normy faktoryzacji podana przez Liniala i Shraibmana jest zasadniczo jedyną dolną granicą znaną ze złożoności komunikacji kwantowej (lub przynajmniej obejmuje wszystkie inne). Czy są jakieś dowody przeciwko ścisłości tego powiązania? Ograniczona normą faktoryzacji...
Oto problem o smaku podobnym do nauki junt: Dane wejściowe: Funkcja , reprezentowana przez wyrocznię członkowską, tzn. Wyrocznię, która dała , zwraca .x f ( x )fa: { 0 , 1 }n→ { - 1 , 1 }f:{0,1}n→{−1,1}f: \{0,1\}^n \rightarrow \{-1,1\}xxxfa( x )f(x)f(x) Cel: Znajdź podmoduł S.SS o wartości { 0 ,...
Dowód Goldreicha i in., Że trzy kolory mogą mieć zerowe dowody wiedzy, wykorzystuje bitowe zaangażowanie w całe zabarwienie wykresu w każdej rundzie [1]. Jeśli wykres ma wierzchołków i krawędzie, bezpieczne hash ma bitów i szukamy błędów prawdopodobieństwo , całkowity koszt komunikacjie b...
Załóżmy, że nasze dane wejściowe są binarne i musimy wyprowadzić ⌊ x / c ⌋ , gdzie c jest jakąś stałą liczbą całkowitą. To tylko zmiana, jeśli c jest potęgą dwóch, ale co z innymi liczbami? Czy możemy to zrobić z obwodem o stałej głębokości dla każdego c ? Co z c = 3 ?xxx⌊x/c⌋⌊x/c⌋\lfloor x/c...
Niech będzie polem. Jak zwykle dla f ∈ k [ x 1 , x 2 , … , x n ] definiujemy L ( f ) jako złożoność linii f względem k w linii prostej . Niech K będzie zbiorem jednomianów f , a mianowicie jednomianów, które występują w f z niezerowym współczynniku.kkkf∈k[x1,x2,…,xn]f∈k[x1,x2,…,xn]f\in...
Chociaż znane są wykładnicze separacje między złożonością kwantowych zapytań o ograniczonym ograniczeniu ( Q ( f)Q(f)Q(f) ) a złożonością deterministycznych zapytań ( D ( f)D(f)D(f) ) lub złożonością losowych zapytań o ograniczonym ograniczeniu ( R ( f)R(f)R(f) ), dotyczą one tylko niektórych...
W przemówieniu Razborowa opublikowano dziwne oświadczenie. Jeśli FACTORING jest trudny, to małe twierdzenie Fermata nie jest możliwe do udowodnienia w S12S21S_{2}^{1} . Co to jest S12S21S_{2}^{1} i dlaczego aktualnych dowodów nie ma w S12S21S_{2}^{1} ?
Powszechnie wiadomo, że pewne klasy NP -Problemy Have dychotomia twierdzeń, które gwarantują, że każde zadanie w klasie jest albo NP -Complete lub jest w P . Najbardziej znanym takim wynikiem jest twierdzenie Schaefera o dychotomii wraz z szeregiem uogólnień. Rozumiem, że udowodnienie tych...