Pytania otagowane jako lower-bounds

pytania o dolne granice funkcji, zwykle złożoność algorytmu lub problem

17
Przykłady ceny abstrakcji?
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]. Oczywiście algorytm Strassena nie przestrzega tego ograniczenia i jest asymptotycznie lepszy niż eliminacja Gaussa. …
9
Optymalne algorytmy zachłanne dla problemów trudnych dla NP
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 dla NP oczywisty i naturalny chciwy / lokalny algorytm skutkuje (możliwym) …
1
Współczynniki Fouriera Funkcje boolowskie opisane przez obwody o ograniczonej głębokości z bramkami AND OR i XOR
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 rzeczywistych na {−1,1}n{−1,1}n\{-1,1\}^n . Suma kwadratów współczynników wynosi …
7
Udowadnianie dolnych granic przez udowodnienie górnych granic
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 informatyce teoretycznej? , podał dwa przykłady ustanawiania dolnych granic …
3
Nietrywialny algorytm obliczania mediany okna przesuwnego
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}) . (Brak oszustw z przybliżeniami; Chciałbym mieć dokładne rozwiązania. Elementy xixix_i są dużymi liczbami całkowitymi.) Istnieje prosty algorytm, który utrzymuje drzewo wyszukiwania …
2
Dolne granice wielkości formuły dla funkcji AC0
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 powyżej standardowego uniwersalnego zestawu bram {AND, OR, NOT}. …
3
Reprezentowanie OR za pomocą wielomianów
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 = 1}^n\left(1-x_i\right)nnn Ale jak mogę pokazać, co wydaje się oczywiste, że jeśli jest wielomianem, który dokładnie reprezentuje funkcję OR (więc ), a następnie ?∀ x ∈ …
2
Najlepsza bieżąca dolna granica dla SAT?
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 może wykorzystywać stany wewnętrzne do symulacji dowolnej stałej liczby komórek taśmy …
Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.