Pytania otagowane jako circuit-complexity

Złożoność obwodu to badanie obwodów ograniczonych przez zasoby i funkcji obliczanych przez takie obwody.

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 …
1
Funkcje boolowskie, w których czułość jest równa czułości bloku
Część pracy nad czułością w porównaniu do czułości bloku miała na celu zbadanie funkcji z możliwie największą luką między s(f)s(f)s(f) i bs(f)bs(f)bs(f) w celu rozstrzygnięcia przypuszczenia, że bs(f)bs(f)bs(f) jest tylko wielomianowo większy niż s(f)s(f)s(f) . Co z przeciwnym kierunkiem? Co wiadomo o funkcjach, w których s(f)=bs(f)s(f)=bs(f)s(f) = bs(f) ? Trywialnie, …
1
Czy BPP vs. P to prawdziwy problem po tym, jak wiemy, że BPP leży w P / poly?
My wiemy (teraz około 40 lat, dzięki Adleman, Bennet Gill), że włączenie BPP ⊆⊆\subseteq P / poly, i jeszcze silniejszy BPP / poli ⊆⊆\subseteq P / poli trzymaj. „/ Poly” oznacza, że ​​pracujemy nierównomiernie (osobny obwód dla każdej długości wejściowej nnn ), podczas gdy P bez tego „/ poly” oznacza, …
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 …
5
Silniejsze pojęcia ujednolicenia?
Jedną z luk, o której zawsze zdawałem sobie sprawę, że tak naprawdę nie rozumiem, jest między niejednorodną i jednolitą złożonością obliczeniową, gdzie złożoność obwodu reprezentuje niejednorodną wersję, a maszyny Turinga to, że rzeczy są jednolite. Przypuszczam, że „jednolity” jest sposobem na ograniczenie klasy algorytmów, np. Niedopuszczenie zupełnie innego obwodu dla …
3
Które problemy
Słynny obraz świata Neila Immermana jest następujący (kliknij, aby powiększyć): Jego „Naprawdę wykonalna” klasa nie obejmuje żadnej innej klasy; moje pytanie brzmi: Co to jest problem AC 0, który jest uważany za niepraktyczny i dlaczego?
1
Wyraźne separacje między obwodami kwantowymi o głębokości poli- i logarytmicznej
Następujący problem pojawia się na liście Aaronsona Dziesięć pół-wielkich wyzwań dla teorii obliczeń kwantowych . Jest B Q P = B P PB Q N CbQP.=bP.P.bQN.do\mathsf{BQP}=\mathsf{BPP}^{\mathsf{BQNC}} Innymi słowy, i „kwantową” część dowolnego algorytmu kwantowej być skompresowane do p o l y l o g (n)polylosol(n)\mathrm{polylog}(n) głębokości, pod warunkiem, że jesteśmy …
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
Co się stanie, jeśli zdefiniujemy P P A D wPPAD{\bf PPAD} taki sposób, że zamiast polytime-maszyny Turinga / obwodu polisize, maszyny logistycznej Turinga lub obwodu A C 0AC0{\bf AC^0} koduje problem? Ostatnio dając szybsze algorytmy Okręgowego spełnialności dla małych obwodów okazało się być ważne, więc zastanawiam się, co się dzieje …
1
Utrzymanie porządku na liście w w Czas
Problem z utrzymaniem porządku (lub „utrzymaniem porządku na liście”) polega na obsłudze operacji: singleton: tworzy listę z jednym elementem, zwraca do niej wskaźnik insertAfter: dany wskaźnik do elementu wstawia nowy element po nim, zwracając wskaźnik do nowego elementu delete: dany wskaźnik do elementu usuwa go z listy minPointer: biorąc pod …
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.