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 problemu ze zmiennymi n w porównaniu do problemu zmiennych n + 1.

Moje pytania to: 1) Jest opis jednolitości tylko w kategoriach obwodów, i 2) Czy można uzyskać jeszcze silniejszą formę jednolitości, a tym samym dać jeszcze bardziej ograniczone pojęcie o tym, jakie skuteczne (lub powściągliwe) algorytmy w P są?

Późne wyjaśnienie: moja intencja w pytaniu 2 dotyczy ograniczonej klasy algorytmów, które „praktycznie” mają taką samą moc jak klasa algorytmów wielomianowych.

Myślę, że odpowiedź na pierwsze pytanie jest przecząca: Obwód ma określoną liczbę wejść, a zatem, IMO, możemy mówić tylko o „rodzinach obwodów”, a nie tylko o jednym jednolitym obwodzie.

Jeśli chodzi o twoje drugie pytanie, możesz zauważyć, że istnieją „jednolite rodziny obwodów”, których opis jest generowany przez maszynę Turinga. To znaczy, niech będzie jednolitą rodziną obwodów, a M niech będzie maszyną Turinga. Następnie, dla każdego n , [ C n ] = M ( 1 N ) , w którym [ C n ] oznacza opis C n .$\{C_n\}$$M$$n$$[C_n] = M(1^n)$$[C_n]$$C_n$

Istnieje kilka klas złożoności poniżej P, zdefiniowanych przez jednolite rodziny obwodów. Na przykład:

jest klasą problemów decyzyjnych rozstrzyganych przezjednoliteobwody boolowskie o wielomianowej liczbie bramek i głębokościO( log i n).$\mathbf{NC}^i$$O(\log^i n)$

Dodając do powyższej odpowiedzi Sadeqa, gdy przyjrzymy się klasom obwodów zawartych w P, można również chcieć przyjrzeć się coraz bardziej restrykcyjnym pojęciom jednorodności.

Najprostszym i najlepiej znanym pojęciem jest P-jednorodności, co jest wymogiem, że istnieje (deterministyczny) Turinga maszynowym M, który tworzy obwód w poli czasu (n) (Suresh rozmów w tym również). Bardziej restrykcyjne wersje jednolitości próbują jeszcze bardziej ograniczyć moc M. Na przykład istnieje również jednolitość Logspace, gdzie M jest teraz wymagane do działania w przestrzeni O (log (n)).$C_n$

Najbardziej restrykcyjnym pojęciem, jakie znam, jest jednorodność DLOGTIME, która jest używana w małych klasach obwodów. Tutaj maszyna M (teraz o dostępie swobodnym) ma tylko czas O (log n) i dlatego nie może zapisywać opisu całego obwodu. Narzucony warunek jest taki, że biorąc pod uwagę i in, M może zapisać i-ty bit opisu obwodu w czasie O (log n).

Więcej informacji można znaleźć w następującym artykule: David A. Mix Barrington, Neil Immerman, Howard Straubing: On Uniformity into NC¹. J. Comput. Syst. Sci. 41 (3): 274–306 (1990).

Jednym ze sposobów „ujednolicenia” obwodów i ujednoliconych obliczeń jest wymaganie procedury o ograniczonej złożoności, która przyjmuje i wysyła obwód doradczy C n . W przypadku P uważam, że wymaganie generatora czasu wielomianowego, który może wykonać powyższe czynności, spowoduje prawidłowe przechwycenie P.$n$$C_n$

Czy istnieje opis jednolitości tylko pod względem obwodów?

Jeśli przez „pod względem obwodów” rozumiesz obwody niejednorodne, wówczas odpowiedź jest przecząca. Jeżeli opis obwodów nie jest jednolity, pozwoli to na użycie funkcji nieobliczalnych do zdefiniowania obwodów, które z kolei będą w stanie obliczyć funkcje nieobliczalne. Zawsze możemy zbudować obwód wielkości obliczający f ( | x | ), gdzie f jest funkcją obliczalną za pomocą wszelkich środków, których używamy do opisania obwodów.$1$$f(|x|)$$f$

$FO$$DLogTime$$AC^0$$FO$

Wydaje mi się, że głównym punktem tutaj jest to, że potrzebujemy jakiegoś modelu obliczeń jednorodnych, aby zdefiniować jednorodność obwodów, jeśli opis obwodów podany jest za pomocą środków, które nie są jednolite, obwody mogą być niejednorodne.

1) Czy istnieje opis jednolitości tylko w odniesieniu do obwodów?

[To jest zredagowana wersja mojej odpowiedzi na to samo pytanie, które zadałeś na blogu Dicka Liptona. Uwaga: nie jestem ekspertem.]

Tak (myślę), co najmniej dwóch różnych rodzajów:

a) Obwody są generowalne przez maszynę Turinga w czasie wielomianowym w wielkości wejściowej problemu (jak wspomniano w niektórych innych odpowiedziach). (Myślę, że to standardowa definicja tego pojęcia).

Obejmuje to każdą rodzinę obwodów, którą moglibyśmy nazwać jednolitą, ale jako definicja pojęcia czasu P, po prostu ogranicza definicję rodzin obwodów do definicji na maszynach Turinga, co może nie być tym, czego chcesz.

b) Jeżeli istnieje 1-wymiarowy automat komórkowy, który ewoluuje problem wejściowy do rozwiązania problemu (w przypadku problemu decyzyjnego rozwiązaniem byłby pojedynczy bit w określonej komórce względem komórek zawierających dane wejściowe, co jest stanem stabilnym CA), w czasie wielomianowym pod względem wielkości wejściowej, odpowiada to układowi, który w prosty sposób jest okresowy w 2D (jedna jednostka powtarzania na komórkę na jednostkę czasu), i którego stan ma znaczenie tylko w kwadracie dużym regionie względnym do czasu rozwiązania.

Jest to bardzo szczególny rodzaj rodziny obwodów jednorodnych, ale wystarczający do rozwiązania wszystkich problemów w P, ponieważ maszynę Turinga można łatwo zakodować jako 1D CA. (Wydaje się to również spełniać definicję jednolitości DLOGTIME wymienioną we wcześniejszej odpowiedzi).

(Jest to podobne do kodowania maszyn Turinga, ponieważ obwody wymienione w odpowiedziach Gowersa na blogu Liptona - w rzeczywistości jeden z nich jest prawdopodobnie identyczny.)

Jednym ze sposobów zakodowania maszyny Turinga jako 1D CA: w każdej komórce reprezentujemy stan taśmy w jednym punkcie, stan, w którym głowa maszyny Turinga byłaby, gdyby był tutaj (którego wartość nie ma znaczenia, jeśli nie jest tutaj) i trochę mówiąc, czy głowa jest tutaj teraz. Oczywiście, każdy taki stan w czasie t zależy tylko od jego bezpośrednich stanów sąsiedztwa w czasie t-1, co jest wszystkim, czego potrzebujemy, aby działał jako CA.