pytania o dolne granice funkcji, zwykle złożoność algorytmu lub problem
Informatyka teoretyczna dostarczyła kilka przykładów „ceny abstrakcji”. Dwa najbardziej znaczące dotyczą eliminacji i sortowania Gaussa. Mianowicie: Wiadomo, że eliminacja Gaussa jest optymalna do, powiedzmy, obliczenia wyznacznika, jeśli ograniczysz operacje do wierszy i kolumn jako całości [1]....
Gdy projektuję algorytm dla nowego problemu, jeśli po pewnym czasie nie mogę znaleźć algorytmu wielomianowego czasu, mogę spróbować udowodnić, że jest to trudny NP. Jeśli mi się uda, wyjaśniłem, dlaczego nie mogłem znaleźć algorytmu czasu wielomianowego. Nie chodzi o to, że wiem na pewno, że P! =...
Jakie są najlepsze dolne granice prądu dla czasu i głębokości obwodu dla
W latach 80. Razborov słynie, że istnieją wyraźne monotoniczne funkcje boolowskie (takie jak funkcja CLIQUE), które wymagają wykładniczo wielu bramek AND i OR do obliczenia. Jednak podstawa {AND, OR} ponad domeną logiczną {0,1} jest tylko jednym przykładem interesującego zestawu bramek, który nie...
Niech PRIMES (inaczej testowanie pierwotności ) będzie problemem: Biorąc pod uwagę liczbę naturalną , czy n jest liczbą pierwszą?nnnnnn Niech FACTORING będzie problemem: Biorąc pod uwagę liczby naturalne , m przy 1 ≤ m ≤ n , czy n ma współczynnik d przy 1 < d < m ?nnnmmm1≤m≤n1≤m≤n1...
Chciwość z braku lepszego słowa jest dobra. Jednym z pierwszych paradygmatów algorytmicznych nauczanym na kursie algorytmów wprowadzających jest podejście zachłanne . Chciwe podejście skutkuje prostymi i intuicyjnymi algorytmami dla wielu problemów w P. Co ciekawe, dla niektórych problemów trudnych...
Kilka lat temu była praca Joela Friedmana związana z dolnymi granicami obwodu z kohomologią Grothendiecka (patrz dokumenty: http://arxiv.org/abs/cs/0512008 , http://arxiv.org/abs/cs/0604024 ). Czy ten sposób myślenia przyniósł jakieś nowe spojrzenie na złożoność logiczną, czy pozostaje raczej...
Niech faff będzie funkcją boolowską i pomyślmy o f jako funkcji od {−1,1}n{−1,1}n\{-1,1\}^n do {−1,1}{−1,1}\{ -1,1 \} . W tym języku ekspansja Fouriera f jest po prostu ekspansją f pod względem kwadratowych wolnych jednomianów. (Te 2n2n2^n monomialów stanowią podstawę dla przestrzeni funkcji...
Niedawny wynik Ryana Williamsa w przełomowym złożoności obwodu w dolnej granicy zapewnia technikę dowodową, która wykorzystuje wynik górnej granicy w celu udowodnienia niższych granic złożoności. Suresh Venkat w swojej odpowiedzi na to pytanie: Czy są jakieś sprzeczne z intuicją wyniki w...
Pytanie: Jaka jest najbardziej znana dolna granica rozmiaru formuły dla jawnej funkcji w AC 0 ? Czy istnieje wyraźna funkcja z dolną granicą ?Ω(n2)Ω(n2)\Omega(n^2) Tło: Podobnie jak większość dolnych granic, dolne granice formuł są trudne do osiągnięcia. Interesują mnie dolne granice formuły...
Muszę obliczyć medianę biegu: Dane wejściowe: , , wektor .nnnkkk(x1,x2,…,xn)(x1,x2,…,xn)(x_1, x_2, \dotsc, x_n) Wyjście: wektor (y1,y2,…,yn−k+1)(y1,y2,…,yn−k+1)(y_1, y_2, \dotsc, y_{n-k+1}) , gdzie yiyiy_i jest medianą (xi,xi+1,…,xi+k−1)(xi,xi+1,…,xi+k−1)(x_i, x_{i+1}, \dotsc, x_{i+k-1})...
Oczywiste jest, że każdy problem, który można rozstrzygnąć w deterministycznej przestrzeni logów ( ), występuje co najwyżej w czasie wielomianowym ( ). Tam jest wiele klas złożoności między i . Przykłady obejmują , , , , , . Uważa się, że .P L P N L L o g C F L N C i S A C i A C i S C i L ≠...
Wiem, że w trywialny sposób funkcja OR dla zmiennych może być dokładnie reprezentowana przez wielomian jako taki: , czyli stopnia .nnnx1,…,xnx1,…,xnx_1,\ldots, x_np(x1,…,xn)p(x1,…,xn)p(x_1,\ldots,x_n)p(x1,…,xn)=1−∏ni=1(1−xi)p(x1,…,xn)=1−∏i=1n(1−xi)p(x_1,\ldots,x_n) = 1-\prod_{i =...
Wielomian f ( x 1 , … , x n )f(x1,…,xn)f(x_1,\ldots,x_n) jest rzutem monotonicznym wielomianu g ( y 1 , … , y m ),g(y1,…,ym)g(y_1,\ldots,y_m) jeśli = poli , i istnieje przypisanie takie, że . Oznacza to, że możliwe jest zastąpienie każdej zmiennej o o zmiennej lub stałą lubm ( n ) π : { y 1 , … ,...
Kontynuując poprzednie pytanie , jakie są najlepsze obecne dolne granice przestrzeni dla SAT? Przez spację dolną rozumiem tutaj liczbę komórek taśmy roboczej używanych przez maszynę Turinga, która używa binarnego alfabetu taśmy roboczej. Stały składnik addytywny jest nieunikniony, ponieważ TM...
W świetle niedawnej otchłani na głębokości 3 wynik (który między innymi daje głębokości 3 arytmetyczna obieg donxndeterminant naC) I mają następujące pytania: Grigoriev i Karpińskiokazałosię2omów(n)dolna granica dla każdego arytmetyczna obwodu głębokości-3 obliczeniowej wyznacznikanxnmacierze nad...
Oprócz (deterministycznej) złożoności komunikacji cc(R)cc(R)cc(R) relacji RRR , inną podstawową miarą ilości potrzebnej komunikacji jest numer podziału protokołu pp(R)pp(R)pp(R) . Zależność między tymi dwoma miarami jest znana aż do stałego współczynnika. Monografia Kushilevitza i Nisana (1997)...
Dokładne sformułowanie tytułu należy do Ananda Kulkarniego (który zaproponował utworzenie tej strony). To pytanie zostało zadane jako przykładowe, ale jestem niesamowicie ciekawy. Wiem bardzo mało o geometrii algebraicznej, a tak naprawdę posiadam jedynie pobieżne, licencjackie rozumienie przeszkód...
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...
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ż...