Jest to klasyczny wynik, że każdy obwód wachlarza 2 AND-OR-NOT, który oblicza PARITY ze zmiennych wejściowych, ma rozmiar co najmniej i jest ostry. (Definiujemy rozmiar jako liczbę bramek AND i OR). Dowodem jest eliminacja bramki i wydaje się, że zawodzi, jeśli pozwolimy na dowolne wbicie. Co jest...
Rozważ następujące uzasadnienie: Niech oznacza złożoność Kołmogorowa ciągu . Twierdzenie Chaitina o niekompletności tak mówiK(x)K(x)K(x)xxx dla jakiejkolwiek spójnej i wystarczająco silny system formalny , istnieje stała (zależnie tylko od formalnego systemu i jego języka) tak, że dla każdej...
Preambuła Interaktywne systemy dowodowe i protokoły Arthura-Merlina zostały wprowadzone przez Goldwassera, Micali i Rackoffa i Babai w 1985 roku. Początkowo sądzono, że ten pierwszy jest potężniejszy od drugiego, ale Goldwasser i Sipser wykazali, że mają taką samą moc ( w odniesieniu do...
(Von Neumann podał algorytm, który symuluje uczciwą monetę, mając dostęp do identycznych monet o tendencyjnym charakterze. Algorytm ten potencjalnie wymaga nieskończonej liczby monet (choć w oczekiwaniu wystarcza ostatecznie ich wiele). Pytanie dotyczy przypadku, gdy dozwolona liczba rzutów monetą...
Bramka AND & OR jest bramką, która ma dwa wejścia i zwraca ich AND oraz OR. Czy obwody wykonane tylko z bramki AND & OR, bez fanouta, mogą wykonywać dowolne obliczenia? Mówiąc ściślej, czy obszar logiczny obliczeń wielomianowych można zredukować do obwodów AND i OR? Moja motywacja do...
Jak wiemy, funkcja - pobiera ( obejmujący ) z pełnego wykresu -vertex , i wyprowadza iff zawiera klik . Zmienne w tym przypadku odpowiadają krawędzi z . Wiadomo (Razborov, Alon-Boppana), że dla funkcja ta wymaga obwodów monotonicznych o wielkości około . C L I Q U E ( n , k )kkkdoL IQ Umi( n , k...
Gdy ogranicza się do wejść - , każdy -circuit oblicza jakąś funkcję . Aby uzyskać funkcję logiczną , możemy po prostu dodać jedną bramkę progową fanin-1 jako bramkę wyjściową. Na wejściu wynikowy próg - obwód wyprowadza następnie jeśli , i wyprowadza jeśli ; próg może być dowolną liczbą całkowitą...
Stosując algorytm przenoszenia patrzeć w przyszłość możemy obliczyć dodatek za pomocą wielomianu głębokość rozmiar 5 (lub 4?) C 0 rodzinę obwodu. Czy można zmniejszyć głębokość? Czy możemy obliczyć dodanie dwóch liczb binarnych przy użyciu wielomianowej rodziny obwodów o głębokości mniejszej niż...
rejestruje ideę skutecznie parallelizable i jeden interpretacja jest to, że problem można rozwiązać w czasie O ( log C n ) za pomocą O ( n k ) równoległych procesorów dla niektórych stałych c , k . Moje pytanie brzmi, czy istnieje analogiczna klasa złożoności, w której czas wynosi n c, a liczba...
Dwa powiązane pytania dotyczące obliczeń na ograniczonej głębokości: 1) Załóżmy, że zaczynasz od n bitów i na początku bitu i może wynosić 0 lub 1 z pewnym prawdopodobieństwem p (i), niezależnie. (Jeśli upraszcza to problem, możemy założyć, że wszystkie p (i) s wynoszą 0,1 lub 1/2.a nawet że...
W artykule „A Compendium of Problems Complete for P” autorstwa Greenlawa, Hoovera i Ruzzo (PS) (PDF) znajduje się lista problemów w P, które nie są znane w NC i nie są znane jako P-complete . (Ta lista obejmuje wszystkie otwarte problemy w doskonałej ankiecie przeprowadzonej przez Karpa i...
Niech będzie klasą wszystkich zwykłych języków.REGREG\mathsf{REG} Znane jest i . Ale czy istnieje jakaś charakterystyka języków w \ mathsf {AC} ^ 0 \ cap \ mathsf {REG} ?AC0⊄REGAC0⊄REG\mathsf{AC}^0 \not\subset \mathsf{REG}REG⊄AC0REG⊄AC0\mathsf{REG} \not\subset...
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...
Możemy obliczyć bramę progową -bitowa przez wielomian wielkości (nieograniczona fan-in) obwody głębokość lg nnnn ? Alternatywnie, czy możemy policzyć liczbę 1s w bitach wejściowych za pomocą tych obwodów?lgnlglgnlgnlglgn\frac{\lg n}{\lg \lg n} Czy ?T C.0⊆ A l t T i m e ( O ( lgnlglgn) , O ( lgn...
Czy istnieją odniesienia, które zawierają szczegółowe informacje na temat dolnych granic obwodu dla konkretnych trudnych problemów pojawiających się w kryptografii, takich jak faktoring liczb całkowitych, problem logarytmu dyskretnego z liczbami pierwszymi / złożonymi i jego wariant nad grupą...
Parzystość i są jak nierozłączne bliźniaki. Tak przynajmniej wyglądało przez ostatnie 30 lat. W świetle wyników Ryana wznowione zostanie zainteresowanie małymi klasami.AC0AC0AC^0 Furst Saxe Sipser do Yao do Hastad są ograniczeniami parzystości i losowymi. Razborov / Smolensky jest przybliżonym...
Myślę, że twierdzenie o hierarchii wielkości dla złożoności obwodów może być dużym przełomem w tej dziedzinie. Czy to ciekawe podejście do separacji klasowej? Motywem tego pytania jest to, że musimy powiedzieć istnieje pewna funkcja, której nie można obliczyć na podstawie obwodów wielkości...
Czy wszystkie funkcje, których waga Fouriera jest skoncentrowana na małych zestawach (lub terminach o niskim stopniu), są obliczane przez obwody
Czy możliwe jest algorytmiczne testowanie, czy liczba obliczalna jest liczbą wymierną czy całkowitą? Innymi słowy, możliwe byłoby dla biblioteki, który implementuje numery obliczalne, aby zapewnić funkcje isIntegerlub isRational? Zgaduję, że nie jest to możliwe i że jest to w jakiś sposób związane...
Interesuje mnie wyraźna funkcja boolowska fa:0 , 1n→0 , 1fa:0,1n→0,1f \colon \\{0,1\\}^n \rightarrow \\{0,1\\}z następującą właściwością: jeśli jest stałe w jakiejś podprzestrzeni afinicznejfafaf , wówczas wymiar tej podprzestrzeni wynosi o ( n ) .0 , 1n0,1n\\{0,1\\}^no ( n )o(n)o(n) Nie jest...