Pytania otagowane jako lower-bounds

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

2
Dolne granice złożoności Gaussa
Określić Gaussa złożoność danego matrycy, tak aby minimalna ilość elementarnych wierszy i kolumn operacji wymaganych do matrycy w postaci górnej trójkątnej. Jest to wielkość od do (poprzez eliminację Gaussa). Pojęcie ma sens w każdej dziedzinie.n×nn×nn \times n000n2n2n^2 Ten problem z pewnością wydaje się bardzo podstawowy i musiał zostać zbadany. O …
2
Status w dolnych granicach obwodu dla obwodów głębokości ograniczonych przez polilog
Złożoność obwodu złożoności jest jednym z głównych obszarów badań w ramach teorii złożoności obwodu. Ten temat ma swoje początki w wynikach takich jak „funkcja parzystości nie jest w ” i „funkcja mod nie jest obliczana przez ”, gdzie jest klasą języków rozstrzygalnych na podstawie niejednolitej, stałej głębokości, wielomianu, nieograniczonego wachlarza …
3
Zwięzłe badanie struktur danych?
Artykuł Fischera w tym miesiącu przypomniał mi, jak mało wiem o sztuce zwięzłych struktur danych i algorytmów ich używania. Dla tych, którzy nie wiedzą o zwięzłych strukturach danych: Biorąc pod uwagę kombinatoryczną strukturę, z (n) odrębnymi konfiguracjami i znaną „użyteczną” reprezentacją . Czy istnieje „zwięzła” struktura danych, która wymaga przechowywania …
2
Liczba bramek binarnych potrzebnych do obliczenia AND i OR n bitów wejściowych jednocześnie
Jaka jest minimalna liczba bramek binarnych potrzebnych do jednoczesnego obliczenia AND i OR bitów wejściowych? Trywialna górna granica wynosi 2 n - 2 . Uważam, że jest to optymalne, ale jak to udowodnić? Nie działa tutaj standardowa technika eliminacji bramki, ponieważ poprzez przypisanie stałej do dowolnej zmiennej wejściowej trywializuje jedno …
1
Czy programowanie dynamiczne nigdy nie jest słabsze niż chciwy?
W złożoności obwodu mamy rozdzielenia mocy różnych modeli obwodów. W złożoności dowodu mamy rozróżnienia między mocami różnych systemów dowodu. Ale w algorytmie wciąż mamy tylko kilka różnic między potęgami paradygmatów algorytmicznych . Moje pytania poniżej mają na celu dotknięcie tego ostatniego problemu w dwóch paradygmatach: Chciwy i Programowanie dynamiczne. Mamy …
1
Jakiś wielomian, który trudno policzyć, ale łatwo go wybrać?
Każdy monotoniczny obwód arytmetyczny , tj. Obwód , oblicza pewną wielomianową wielomian z nieujemnymi współczynnikami całkowitymi. Biorąc pod uwagę wielomian , obwódF ( x 1 , … , x n ) f ( x 1 , … , x n ){+,×}{+,×}\{+,\times\}F(x1,…,xn)F(x1,…,xn)F(x_1,\ldots,x_n)f(x1,…,xn)f(x1,…,xn)f(x_1,\ldots,x_n) oblicza fff jeśli F(a)=f(a)F(a)=f(a)F(a)=f(a) dla wszystkich a∈Nna∈Nna\in \mathbb{N}^n ; …
1
Czy dowody, że permanent nie jest w mundurze
Jest to kontynuacja tego pytania i jest związana z tym pytaniem Shivy Kinali. Wydaje się, że dowody w tych dokumentach ( Allender , Caussinus-McKenzie-Therien-Vollmer , Koiran-Perifel ) używają twierdzeń hierarchicznych. Chcę wiedzieć, czy dowody są „ czystymi ” twierdzeniami o diagonalizacji, czy też używają czegoś więcej niż zwykła diagonalizacja. Więc …
3
Postęp w ogólnym problemie z wysokością gwiazdy?
(Uogólniona) wysokość gwiazdy w języku jest minimalnym zagnieżdżeniem gwiazd Kleene wymaganym do przedstawienia języka za pomocą rozszerzonego wyrażenia regularnego. Przypomnijmy, że rozszerzonym wyrażeniem regularnym ponad skończonych alfabet spełnia następujące:ZAAA (1) i są rozszerzone wyrażenia regularne dla wszystkich A ∈∅ , 1∅,1\emptyset, 1zaaaa ∈ Aa∈Aa\in A (2) Dla wszystkich rozszerzonych wyrażeń …
1
Monotoniczna złożoność obwodu arytmetycznego elementarnych wielomianów symetrycznych?
W kkk -tej elementarne wielomian symetryczny Snk(x1,…,xn)Skn(x1,…,xn)S_k^n(x_1,\ldots,x_n) jest sumą wszystkich produktów różnych zmiennych. Interesuje mnie złożoność obwodu arytmetycznego monotonicznego tego wielomianu. Prosty algorytm programowania dynamicznego (jak również ryc. 1 poniżej) daje obwód z bramkami .(nk)(nk)\binom{n}{k}kkk(+,×)(+,×)(+,\times)(+,×)(+,×)(+,\times)O(kn)O(kn)O(kn) Pytanie: Czy znana jest dolna granica ? Ω(kn)Ω(kn)\Omega(kn) obwód jest skośna , jeżeli co najmniej …
3
Jak mogę pokazać, że problem Gap-P jest poza #P
Istnieje wiele problemów w kombinatorycznej teorii reprezentacji i geometrii algebraicznej, dla których nie jest znana formuła dodatnia. Myślę o kilku przykładach, ale pozwólcie, że obliczę współczynniki Kroneckera jako mój przykład. Zwykle pojęcie „formuły dodatniej” nie jest precyzyjnie zdefiniowane w kombinatorykach, ale z grubsza oznacza „opis jako liczność zbioru rozsądnie wyraźnego”. …
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.