Pytania oznaczone «circuit-complexity»

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...

EDYCJA (22 sierpnia 2011 r.): Jeszcze bardziej upraszczam pytanie i wyróżniam je. Być może to prostsze pytanie będzie miało łatwą odpowiedź. Przekreślę także wszystkie części pierwotnego pytania, które nie są już istotne. (Podziękowania dla Stasysa Jukny i Ryana O'Donnella za częściową odpowiedź...

Dolna granica Bluma jest najlepiej znaną dolną granicą obwodu w całej bazie dla jawnej funkcji f : { 0 , 1 } n → { 0 , 1 } , por. Odpowiedź Jukny na to pytanie zawiera powiązane wyniki.3 n - o ( n )3)n-o(n)3n-o(n)fa: { 0 , 1 }n→ { 0 , 1 }fa:{0,1}n→{0,1}f : \{0,1\}^n \to \{0,1\} Jakie są...

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...

Niedeterministyczny obwód boolowski ma, oprócz zwykłych danych wejściowych , zbiór danych „niedeterministycznych” y = ( y 1 , … , y m ) . Niedeterministyczny obwód C przyjmuje wejście x, jeśli istnieje y takie, że wyjście obwodu 1 jest włączone ( x , y ) . Analogicznie do P / p o l...

Jak dobrze wiadomo PARITY nie może być wykonane w obwodach o stałej wielkości o wielkiej wielkości, aw rzeczywistości obwody stałe wymagają liczby EXP bramek. Co z obwodami QUANTUM? a) Czy PARITY można wykonać za pomocą obwodu kwantowego, który ma stałą głębokość i liczbę bramek? b) Czy moje...

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,...

Wiadomo, że wielkość najmniej -circuits obliczania funkcji parzystości dokładnie równa 3 ( n - 1 ) . Dowód dolnej granicy oparty jest na metodzie eliminacji bramki.U2U2U_23(n−1)3(n−1)3(n-1) Ostatnio zauważyłem, że metoda eliminacji bramki działa dobrze również w przypadku niedeterministycznych...

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...

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...

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”...

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...

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...

Dowody naturalne stanowią barierę dla udowodnienia niższych granic złożoności obwodu funkcji boolowskich. Nie bezpośrednio wynika, takiej bariery dla udowodnienia niższe granice na obwód złożoności. Czy jest jakiś postęp w identyfikowaniu takich barier? Czy istnieją inne bariery w ustawieniu...

tło Formuła „read-once” na zbiorze bramek (zwana również podstawą) to formuła, w której każda zmienna wejściowa pojawia się jeden raz. Formuły do ​​odczytu raz są powszechnie badane na podstawie De Morgana (która ma 2-bitowe bramki AND i OR oraz 1-bitową bramkę NOT) i pełnej bazy binarnej (która...

Załóżmy, że otrzymujemy zestaw n zmiennych logicznych x_1, ..., x_n oraz zestaw funkcji m y_1 ... y_m, gdzie każdy y_i jest XOR (danego) podzbioru tych zmiennych. Celem jest obliczenie minimalnej liczby operacji XOR, które należy wykonać, aby obliczyć wszystkie te funkcje y_1 ... y_m. Zauważ, że...

Chciałbym zapytać o dobre teksty wprowadzające złożoność obwodu. Pomocne będą również wszelkie wskazówki dotyczące ostatnich postępów i otwartych problemów w tej

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...

To pytanie można zadać albo w ramach złożoności obwodów obwodów boolowskich, albo w ramach teorii złożoności algebraicznej, lub prawdopodobnie w wielu innych ustawieniach. Łatwo jest wykazać, licząc argumenty, że istnieją funkcje logiczne na wejściach N, które wymagają wykładniczo wielu bramek...

W artykule „ Naturalne dowody” Razborova-Rudicha , strona 6, w części, w której dyskutują, że istnieją „silne dowody dolnej granicy na modele obwodów monotonicznych ” i to, jak pasują do zdjęcia, są następujące zdania: Tutaj nie chodzi o konstruktywność - wszystkie właściwości użyte w tych...