Клас складності NC

В теорії складності обчислень класом NC (від англ. Nick’s Class) називають множину задач розв'язності, що розв'язуються за полілогарифмічний час на паралельному комп'ютері з поліноміальним числом процесорів. Іншими словами, задача належить до класу NC, якщо існують константи ${\displaystyle k}$ і ${\displaystyle c}$ такі, що її можна розв'язати за час ${\displaystyle O(\log ^{c}n)}$ при використанні ${\displaystyle O(n^{k})}$ паралельних процесорів. Стівен Кук^[1][2] назвав його «класом Ніка» на честь Ніка Піппенжера^[en], який широко дослідив^[3] схеми з полілогарифмічною глибиною і поліноміальним розміром^[4].

Так само, як клас P можна вважати класом податливих задач (теза Кобгема^[en]), так і NC можна вважати класом задач, які можна ефективно розв'язати на паралельному комп'ютері.^[5] NC — це підмножина P, тому що паралельні полілогарифмічні обчислення можна симулювати за допомогою послідовних поліноміальних обчислень. Невідомо, чи NP = P, але більшість учених вважає, що ні, з чого випливає, що найпевніше існують податливі задачі, які послідовні «від природи», і не можуть бути істотно прискореними за використання паралелізму. Так само, як клас NP-повних задач можна вважати класом «найпевніше непіддатливих» задач, так і клас P-повних задач^[en], при зведенні до NC, можна вважати «найпевніше непаралелізовним» або «найпевніше послідовним від природи».

Паралельний комп'ютер у визначенні можна вважати паралельною машиною з довільним доступом (PRAM — від англ. parallel, random-access machine). Це паралельний комп'ютер із центральним пулом пам'яті, будь-який процесор якого може отримати доступ до будь-якого біта за сталий час. На визначення NC не впливає спосіб, за допомогою якого PRAM здійснює одночасний доступ декількох процесорів до одного біта.

NC можна визначити, як множину задач розв'язності, розв'язуваних розподіленою булевою схемою^[en] з полілогарифмічною глибиною і поліноміальним числом вентилів.

Задачі в NC

NC включає багато задач, зокрема:

• Додавання, множення і ділення цілих чисел;
• Множення матриць, підрахунок їх рангу, детермінанта, оберненої матриці;
• Поліноміальний НСД;
• Знаходження найбільшого парування.

Часто алгоритми для цих задач придумувалися окремо і не могли бути наївною адаптацією відомих алгоритмів — метод Гауса і алгоритм Евкліда покладаються на те, що операції виконуються послідовно.

Ієрархія NC

NCⁱ — це множина задач розв'язності, розв'язуваних розподіленими булевими схемами з поліноміальною кількістю вентилів (з числом входів не більше двох) і глибиною ${\displaystyle O(\log ^{i}n)}$, або розв'язуваних за час ${\displaystyle O(\log ^{i}n)}$ паралельним комп'ютером з поліноміальним числом процесорів. Очевидно,

${\displaystyle {\mathsf {NC}}^{1}\subseteq {\mathsf {NC}}^{2}\subseteq \cdots \subseteq {\mathsf {NC}}^{i}\subseteq \cdots {\mathsf {NC}},}$

що є NC-ієрархією.

Ми можемо пов'язати класи NC з класами пам'яті L, NL^[6] і AC^[7]:

${\displaystyle {\mathsf {NC}}^{1}\subseteq {\mathsf {L}}\subseteq {\mathsf {NL}}\subseteq {\mathsf {AC}}^{1}\subseteq {\mathsf {NC}}^{2}\subseteq {\mathsf {P}}.}$

Класи NC і AC однаково визначені, за винятком необмеженості кількості входів у вентилів для класу AC. Для кожного ${\displaystyle i}$ виконується^[5][7]:

${\displaystyle {\mathsf {NC}}^{i}\subseteq {\mathsf {AC}}^{i}\subseteq {\mathsf {NC}}^{i+1}.}$

Наслідком цього є NC = AC.^[8] Відомо, що обидва включення строгі для ${\displaystyle i=0}$.^[5] Схожим чином можемо отримати, що NC еквівалентний множині задач, що розв'язуються на змінній машині Тюрінга^[en] з числом виборів на кожному кроці не більшим, ніж два, і з O(log n) пам'яті та ${\displaystyle (\log n)^{O(1)}}$ альтераціями.^[9]

Нерозв'язана задача: чи є NC власним?

Одне з великих відкритих питань теорії складності обчислень — чи є власним кожне вкладення NC-ієрархії. Як зауважив Пападімітріу, якщо для якогось ${\displaystyle i}$ виконується NCⁱ = NCⁱ⁺¹, то NCⁱ = NC^j для всіх ${\displaystyle j\geqslant i}$, і, як наслідок, NCⁱ = NC. Це спостереження називають згортанням NC-ієрархії, тому що навіть з однієї рівності в ланцюзі вкладень:

${\displaystyle {\mathsf {NC}}^{1}\subseteq {\mathsf {NC}}^{2}\subseteq \cdots }$

випливає, що вся NC-ієрархія «згортається» до якогось рівня ${\displaystyle i}$. Таким чином, можливі два варіанти:

1. ${\displaystyle {\mathsf {NC}}^{1}\subset \cdots \subset {\mathsf {NC}}^{i}\subset \cdots \subset {\mathsf {NC}}^{i+j}\subset \cdots {\mathsf {NC}}}$
2. ${\displaystyle {\mathsf {NC}}^{1}\subset \cdots \subset {\mathsf {NC}}^{i}=\cdots ={\mathsf {NC}}^{i+j}=\cdots {\mathsf {NC}}.}$

Поширена думка, що істинне саме (1), хоча поки не виявлено ніяких доказів щодо істинності того чи іншого твердження.

Теорема Баррінгтона

Розгалужена програма з ${\displaystyle n}$ змінними, шириною ${\displaystyle k}$ і довжиною ${\displaystyle m}$ складається з послідовності інструкцій довжини ${\displaystyle m}$. Кожна інструкція — це трійка ${\displaystyle (i,p,q)}$, де ${\displaystyle i}$ — це індекс змінної, яку потрібно перевірити ${\displaystyle (1\leq i\leq n)}$, а ${\displaystyle p}$ і ${\displaystyle q}$ — це функції перестановки із ${\displaystyle \{1,2,...,k\}}$ в ${\displaystyle \{1,2,...,k\}}$. Число ${\displaystyle 1,2,...,k}$ називаються станами розгалуженої програми. Програма починається в стані 1, і кожна інструкція ${\displaystyle (i,p,q)}$ змінює стан ${\displaystyle x}$ на ${\displaystyle p(x)}$ або ${\displaystyle q(x)}$, залежно від того, дорівнює ${\displaystyle i}$-та змінна 0 чи 1.

Сімейство розгалужених програм складається з розгалужених програм з ${\displaystyle n}$ змінними для кожного ${\displaystyle n}$.

Легко показати, що будь-яку мову ${\displaystyle L}$ на ${\displaystyle \{0,1\}}$ можна розпізнати сімейством розгалужених програм з шириною 5 і експоненціальною довжиною, або сімейством з експоненціальною шириною і лінійною довжиною.

Кожну регулярну мову на ${\displaystyle \{0,1\}}$ можна розпізнати сімейством розгалужених програм зі сталою шириною і лінійним числом інструкцій (оскільки ДСА можна перетворити на розгалужену програму). BWBP позначає клас мов, що розпізнаються сімейством розгалужених програм з обмеженою шириною і поліноміальною довжиною (англ. BWBP — branching programs of bounded width and polynomial length)^[10].

Теорема Баррінгтона^[11] стверджує, що BWBP — це точно нерозподілений NC¹. Доведення теореми використовує нерозв'язність групи симетрії ${\displaystyle S_{5}}$^[10].

Доказ теореми Баррінгтона

Доведемо, що розгалужену програму (РП) зі сталою шириною і поліноміальним розміром можна перетворити на схему з NC¹.

Від супротивного: нехай є схема C із NC¹. Без обмеження загальності, вважатимемо, що в ній використовуються тільки вентилі І і НЕ.

Визначення: РП називається такою, що ${\displaystyle \sigma }$-обчислює булеву функцію ${\displaystyle f}$ або ${\displaystyle (\sigma -f)}$, якщо при ${\displaystyle f=0}$ вона дає результат — тотожну перестановку, а при ${\displaystyle f=1}$ її результат — ${\displaystyle \sigma }$-перестановка. Оскільки наша схема C описує якусь булеву функцію ${\displaystyle f}$ і тільки її, можемо взаємно замінювати ці терміни.

Для доведення використаємо дві леми:

Лема 1. Якщо є РП, що ${\displaystyle \sigma }$-обчислює ${\displaystyle f}$, то існує і РП, що ${\displaystyle \sigma ^{-1}}$-обчислює ${\displaystyle f}$ (тобто, рівна ${\displaystyle id}$ при ${\displaystyle f=0}$, і рівна ${\displaystyle \sigma ^{-1}}$ при ${\displaystyle f=1}$).

Доведення: оскільки ${\displaystyle \sigma }$ і ${\displaystyle \sigma ^{-1}}$ — цикли, а будь-які два цикли є спряженими, то існує така перестановка ${\displaystyle \pi }$, що ${\displaystyle \sigma ^{-1}}$ = ${\displaystyle \pi \sigma \pi ^{-1}}$. Тоді домножимо на ${\displaystyle \pi }$ перестановки ${\displaystyle p_{1}}$ і ${\displaystyle q_{1}}$ з першої інструкції РП зліва (щоб отримати перестановки ${\displaystyle {\pi }p_{1}}$ і ${\displaystyle {\pi }q_{1}}$), а перестановки з останньої інструкції домножимо на ${\displaystyle \pi ^{-1}}$ справа (отримаємо ${\displaystyle p_{n}\pi ^{-1}}$ і ${\displaystyle q_{n}\pi ^{-1}}$). Якщо до наших дій (без обмеження загальності) ${\displaystyle {p_{1}}{p_{2}}...{p_{n}}}$ дорівнював ${\displaystyle id}$, то тепер результат буде ${\displaystyle {\pi }id{\pi }^{-1}=id}$, а якщо дорівнював ${\displaystyle \sigma }$, то результат дорівнює ${\displaystyle \pi \sigma \pi ^{-1}=\sigma ^{-1}}$. Так, ми отримали РП, що ${\displaystyle \sigma ^{-1}}$-обчислює ${\displaystyle f}$, такої ж довжини (кількість інструкцій не змінилася).

Примітка: якщо домножити вивід РП ${\displaystyle (\sigma ^{-1}-f)}$ на ${\displaystyle \sigma }$ справа, то очевидним чином отримаємо РП, що ${\displaystyle \sigma }$-обчислює функцію ${\displaystyle {\neg }f}$.

Лема 2. Якщо є дві РП: що ${\displaystyle \sigma }$-обчислює ${\displaystyle f}$ і ${\displaystyle \gamma }$-обчислює ${\displaystyle t}$ з довжинами ${\displaystyle l_{1}}$ і ${\displaystyle l_{2}}$, де ${\displaystyle \sigma }$ і ${\displaystyle \gamma }$ — 5-циклічні перестановки, то існує РП з 5-циклічною перестановкою ${\displaystyle \varepsilon =\gamma \sigma \gamma ^{-1}\sigma ^{-1}}$ така, що РП ${\displaystyle \varepsilon }$-обчислює ${\displaystyle f{\wedge }t}$, і її розмір не перевищує ${\displaystyle 2(l_{1}}$ + ${\displaystyle l_{2})}$.

Доведення: викладемо «в ряд» інструкції чотирьох РП: ${\displaystyle (\gamma -t)}$, ${\displaystyle (\sigma -f)}$, ${\displaystyle (\gamma ^{-1}-t)}$, ${\displaystyle (\sigma ^{-1}-f)}$ (будуємо зворотні за лемою 1). Якщо одна або обидві функції видають 0, то результат великої програми ${\displaystyle \varepsilon =id}$: наприклад, при ${\displaystyle f=0,t=1,\varepsilon =id{\sigma }id{\sigma }^{-1}=id}$. Якщо обидві функції видають 1, то ${\displaystyle \varepsilon =\gamma \sigma \gamma ^{-1}\sigma ^{-1}}$. Тут ${\displaystyle \gamma \sigma \gamma ^{-1}\sigma ^{-1}\neq id<=>\gamma \sigma \neq \sigma \gamma }$, що істинне, оскільки ці перестановки 5-циклічні (через нерозв'язність групи симетрії ${\displaystyle S_{5}}$). Довжина нової РП обчислюється за визначенням.

${\displaystyle }$Доведення теореми

Доводитимемо за індукцією. Припустимо, що ми маємо схему C зі входами ${\displaystyle x_{1},...,x_{n}}$ і що для всіх підсхем D і 5-циклічних перестановок ${\displaystyle \sigma }$ існує РП, що ${\displaystyle \sigma }$-обчислює D. Покажемо, що для всіх 5-перестановок ${\displaystyle \sigma }$ існує РП, що ${\displaystyle \sigma }$-обчислює C.

• Якщо схема C видає ${\displaystyle x_{i}}$, то РП має одну інструкцію: перевірити значення ${\displaystyle x_{i}}$ (0 або 1), і віддати ${\displaystyle id}$ або ${\displaystyle \sigma }$ (відповідно).
• Якщо схема C видає ${\displaystyle \neg }$A для якоїсь іншої схеми A, за приміткою до леми 1 створимо РП, що ${\displaystyle \sigma }$-обчислює ${\displaystyle \neg }$A.
• Якщо схема C видає A${\displaystyle \wedge }$B для схем A і B, створимо потрібну РП за лемою 2.

Розмір кінцевої розгалуженої програми не перевершує ${\displaystyle 4^{d}}$, де ${\displaystyle d}$ — глибина схеми. Якщо у схеми логарифмічна глибина, то в РП поліноміальна довжина.

Примітки

Посилання

• Arora, Sanjeev; Barak, Boaz (2009). Computational complexity. A modern approach. Cambridge University Press. ISBN 978-0-521-42426-4. Zbl 1193.68112.
• Clote, Peter; Kranakis, Evangelos (2002). Boolean functions and computation models. Texts in Theoretical Computer Science. An EATCS Series. Berlin: Springer-Verlag. ISBN 3-540-59436-1. Zbl 1016.94046.
• Greenlaw, Raymond, James Hoover, and Walter Ruzzo. Limits To Parallel computation; P-Completeness Theory. [Архівовано 4 Червня 2013 у Wayback Machine.] Архивная копия від 4 червня 2013 на Wayback Machine ISBN 0-19-508591-4
• Kozen, Dexter C. (1992). The design and analysis of algorithms. Lectures 28 — 34 and 36
• Kozen, Dexter C. (2006). Theory of Computation. Texts in Computer Science. Springer-Verlag. ISBN 1-84628-297-7. Zbl 1102.68025. Lecture 12: Relation of NC to Time-Space Classes
• Papadimitriou, Christos (1993). Section 15.3: The class NC. Computational Complexity (вид. 1st). Addison Wesley. с. 375–381. ISBN 0-201-53082-1.
• Straubing, Howard (1994). Finite automata, formal logic, and circuit complexity. Progress in Theoretical Computer Science. Basel: Birkhäuser. ISBN 3-7643-3719-2. Zbl 0816.68086.
• Vollmer, Heribert (1998). Introduction to circuit complexity. A uniform approach. Texts in Theoretical Computer Science. Berlin: Springer-Verlag. ISBN 3-540-64310-9. Zbl 0931.68055.

Нормативний контроль Freebase: /m/05jrf