Silniejsze pojęcia ujednolicenia?

16

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.

cc.complexity-theory circuit-complexity

— Gil Kalai
źródło

Czy możesz rozwinąć znaczenie „praktycznie ma taką samą moc”?

— MS Dousti,

Mam na myśli, że wszystkie algorytmy w P, które spotykamy praktycznie znajdują się w tej (hipotetycznej) klasie ograniczonej. Nie mam więc na myśli klas, które są znane (lub są przypuszczane), że pomijają określony algorytm wielomianowy, taki jak AC_0 lub NC ^ i nie są tym, o czym mówię.

— Gil Kalai

2

W przypadku pytania 2 klasą funkcji obliczalnych przez obwody jednolite o wielkości wielomianowej LOGSPACE jest P. (I nadal otrzymujesz P nawet przy niektórych klasach złożoności mniejszych niż LOGSPACE, jeśli poprawnie zdefiniujesz jednorodność.) Tak więc narzucenie bardziej surowych warunków jednorodności nie ogólnie zmniejszają moc algorytmów czasu wielomianowego.

— Peter Shor,

8

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 niech będzie maszyną Turinga. Następnie, dla każdego , , w którym oznacza opis . $\{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ści. $\mathbf{NC}^i$ $O(\log^i n)$

— MS Dousti
źródło

7

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

— Srikanth
źródło

1

Link do artykułu: dx.doi.org/10.1016/0022-0000(90)90022-D

— Suresh Venkat

Jeśli M ma zamiar zapisać i-ty bit opisu obwodu w O (log n), nie oznacza to, że jeśli obwód ma rozmiar O (n), jest to równoważne z zezwoleniem maszynie na wygenerowanie cały obwód w O (n log n)?

— M. Alaggan,

1

To nie wydaje się równoważne. Wykazałeś, że powyższe (Barrington i in.) Pojęcie jednolitości jest co najmniej tak silne, jak proponowane pojęcie jednolitości. Przeciwnie, nie jest jasne. W szczególności nie jest dla mnie jasne, czy spełnione są następujące warunki: biorąc pod uwagę rodzinę obwodów o wielkości

które mogą być generowane przez TM w czasie

, wymyśl TM, która, biorąc pod uwagę

a

, wytwarza się

th bitów

w czasie

. W rzeczywistości nie sądzę, że to prawda.

O (n)

$O(n)$

O (n \log n)

$O(n\log n)$

i

$i$

n

$n$

i

$i$

C_{n}

$C_n$

O (\log n)

$O(\log n)$

— Srikanth

Zgadzam przykładem licznik będzie TM, że w związku

i

, generuje

-ty bit w

, z wyjątkiem ostatnich bitów, do których następuje

. Dzięki za podpowiedź :)

i

$i$

n

$n$

i

$i$

O (1)

$O(1)$

O (n \log n)

$O(n \log n)$

— M. Alaggan

Nie chodzi o to, że rodziny obwodów z mundurami X dają te same zestawy rodzin dla różnych X, ale że funkcje, które mogą być obliczone przez rodziny obwodów z mundurami X są takie same dla różnych X.

— Peter Shor

6

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

— Suresh Venkat
źródło

Generator LOGSPACE dla obwodu będzie również działał dobrze, aby przechwycić P.

— Peter Shor

5

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

— Kaveh
źródło

1

O (1)

$O(1)$

A l t T i m e (O (1), O (\lg n))

$AltTime(O(1),O(\lg n))$ .

— Kaveh

4

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.