Перегляд вихідного коду сторінки Клас складності NC

В [[Теорія складності обчислень|теорії складності обчислень]] '''класом NC''' (від {{lang-en|Nick’s Class}}) називають множину [[Проблема вибору|задач розв'язності]], що розв'язуються за полілогарифмічний час на [[Паралельні обчислення|паралельному комп'ютері]] з поліноміальним числом процесорів. Іншими словами, задача належить до класу NC, якщо існують константи <math>k</math> і <math>c</math> такі, що її можна розв'язати за час <math>O(\log^cn)</math> при використанні <math>O(n^k)</math> паралельних процесорів. [[Стівен Кук]]<ref>{{Cite journal|title=Towards a complexity theory of synchronous parallel computation. D L'Enseignement mathematique 27|url=http://citeseerx.ist.psu.edu/showciting?cid=1672592|language=en|journal=|accessdate=10 Березня 2022|archive-date=10 Березня 2022|archive-url=https://web.archive.org/web/20220310162127/http://citeseerx.ist.psu.edu/showciting?cid=1672592}}</ref><ref>{{Cite journal|last=Cook|first=Stephen A.|date=1985-01-01|title=A taxonomy of problems with fast parallel algorithms|journal=Information and Control|series=International Conference on Foundations of Computation Theory|language=en|volume=64|issue=1|pages=2–22|doi=10.1016/S0019-9958(85)80041-3|issn=0019-9958|doi-access=free}}</ref> назвав його «класом Ніка» на честь {{Не перекладено|Нік Піппенжер|Ніка Піппенжера|en|Nick Pippenger}}, який широко дослідив<ref>{{Cite journal|last=Pippenger|first=Nicholas|date=1979|title=On simultaneous resource bounds|url=https://www.infona.pl//resource/bwmeta1.element.ieee-art-000004568025|journal=20th Annual Symposium on Foundations of Computer Science (SFCS 1979)|language=English|pages=307–311|doi=10.1109/SFCS.1979.29|issn=0272-5428}}</ref> схеми з полілогарифмічною глибиною і поліноміальним розміром<ref name="AB120">Arora & Barak (2009) p.120</ref>.

Так само, як клас [[Клас складності P|P]] можна вважати класом податливих задач ({{Не перекладено|теза Кобгема||en|Cobham's thesis}}), так і NC можна вважати класом задач, які можна ефективно розв'язати на паралельному комп'ютері.<ref name="AB118">Arora & Barak (2009) p.118</ref> NC&nbsp;— це підмножина P, тому що паралельні полілогарифмічні обчислення можна симулювати за допомогою послідовних поліноміальних обчислень. Невідомо, чи NP = P, але більшість учених вважає, що ні, з чого випливає, що найпевніше існують податливі задачі, які послідовні «від природи», і не можуть бути істотно прискореними за використання паралелізму. Так само, як клас [[NP-повна задача|NP-повних задач]] можна вважати класом «найпевніше непіддатливих» задач, так і клас {{Нп|Клас складності P-повні|P-повних задач|en|P-complete}}, при зведенні до NC, можна вважати «найпевніше непаралелізовним» або «найпевніше послідовним від природи».

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

NC можна визначити, як множину задач розв'язності, розв'язуваних {{Нп|Булева схема|розподіленою булевою схемою|en|Boolean circuit}} з полілогарифмічною глибиною і поліноміальним числом [[Логічний вентиль|вентилів]].

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

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

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

== Ієрархія NC ==
'''NC'''<sup>''i''</sup>&nbsp;— це множина задач розв'язності, розв'язуваних розподіленими булевими схемами з поліноміальною кількістю вентилів (з числом входів не більше двох) і глибиною <math>O(\log^in)</math>, або розв'язуваних за час <math>O(\log^in)</math> паралельним комп'ютером з поліноміальним числом процесорів. Очевидно,

: <math>\mathsf{NC}^1 \subseteq \mathsf{NC}^2 \subseteq \cdots \subseteq \mathsf{NC}^i \subseteq \cdots \mathsf{NC},</math>

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

Ми можемо пов'язати класи '''NC''' з класами пам'яті '''[[Класи складності L і NL|L]]''', '''[[Класи складності L і NL|NL]]'''<ref>Papadimitriou (1994) Theorem 16.1</ref> і '''[[Клас складності AC|AC]]'''<ref name="CK437">Clote & Kranakis (2002) p.437</ref>:

: <math> \mathsf{NC}^1 \subseteq \mathsf{L} \subseteq \mathsf{NL} \subseteq \mathsf{AC}^1 \subseteq \mathsf{NC}^2 \subseteq \mathsf{P}.</math>

Класи NC і AC однаково визначені, за винятком необмеженості кількості входів у вентилів для класу AC. Для кожного <math>i</math> виконується<ref name="AB118"/><ref name="CK437"/>:

: <math>\mathsf{NC}^i \subseteq \mathsf{AC}^i \subseteq \mathsf{NC}^{i+1}.</math>

Наслідком цього є '''NC''' = '''AC'''.<ref name="CK12">Clote & Kranakis (2002) p.12</ref> Відомо, що обидва включення строгі для <math>i = 0</math>.<ref name="AB118"/> Схожим чином можемо отримати, що NC еквівалентний множині задач, що розв'язуються на {{Нп|Змінна машина Тюрінга|змінній машині Тюрінга|en|Alternating Turing machine}} з числом виборів на кожному кроці не більшим, ніж два, і з ''O''(log ''n'') пам'яті та <math>(\log n)^{O(1)}</math> альтераціями.<ref>{{Cite journal|last=S. Bellantoni and I. Oitavem|year=2004|title=Separating NC along the delta axis|journal=Theoretical Computer Science|volume=318|issue=1–2|pages=57–78|doi=10.1016/j.tcs.2003.10.021}}</ref>

=== Нерозв'язана задача: чи є NC власним? ===
Одне з великих відкритих питань [[Теорія складності обчислень|теорії складності обчислень]]&nbsp;— чи є власним кожне вкладення NC-ієрархії. Як зауважив Пападімітріу, якщо для якогось <math>i</math> виконується '''NC'''<sup>''i''</sup> = '''NC'''<sup>''i''+1</sup>, то '''NC'''<sup>''i''</sup> = '''NC'''<sup>''j''</sup> для всіх <math>j \geqslant i</math>, і, як наслідок, '''NC'''<sup>''i''</sup> = '''NC'''. Це спостереження називають згортанням NC-ієрархії, тому що навіть з однієї рівності в ланцюзі вкладень:

: <math>\mathsf{NC}^1 \subseteq \mathsf{NC}^2 \subseteq \cdots</math>

випливає, що вся '''NC'''-ієрархія «згортається» до якогось рівня <math>i</math>. Таким чином, можливі два варіанти:

# <math>\mathsf{NC}^1 \subset \cdots \subset \mathsf{NC}^i \subset \cdots \subset \mathsf{NC}^{i+j} \subset \cdots \mathsf{NC}</math>
# <math>\mathsf{NC}^1 \subset \cdots \subset \mathsf{NC}^i = \cdots = \mathsf{NC}^{i+j} = \cdots \mathsf{NC}.</math>

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

== Теорема Баррінгтона ==
'''Розгалужена програма''' з <math>n</math> змінними, шириною <math>k</math> і довжиною <math>m</math> складається з послідовності інструкцій довжини <math>m</math>. Кожна інструкція&nbsp;— це трійка <math>(i, p, q)</math>, де <math>i</math>&nbsp;— це індекс змінної, яку потрібно перевірити <math>(1 \leq i \leq n)</math>, а <math>p</math> і <math>q</math>&nbsp;— це функції [[Перестановка|перестановки]] із <math>\{1, 2, ..., k\}</math> в <math>\{1, 2, ..., k\}</math>. Число <math>1, 2, ..., k</math> називаються станами розгалуженої програми. Програма починається в стані 1, і кожна інструкція <math>(i, p, q)</math> змінює стан <math>x</math> на <math>p(x)</math> або <math>q(x)</math>, залежно від того, дорівнює <math>i</math>-та змінна 0 чи 1.

Сімейство розгалужених програм складається з розгалужених програм з <math>n</math> змінними для кожного <math>n</math>.

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

Кожну [[Регулярна мова|регулярну мову]] на <math>\{0,1\}</math> можна розпізнати сімейством розгалужених програм зі сталою шириною і лінійним числом інструкцій (оскільки [[Детермінований скінченний автомат|ДСА]] можна перетворити на розгалужену програму). '''BWBP''' позначає клас мов, що розпізнаються сімейством розгалужених програм з обмеженою шириною і поліноміальною довжиною ({{lang-en|BWBP}}&nbsp;— branching programs of bounded width and polynomial length)<ref name="CK50">Clote & Kranakis (2002) p.50</ref>.

'''Теорема Баррінгтона'''<ref name="Bar89">{{Cite journal|last=Barrington|first=David A.|year=1989|title=Bounded-Width Polynomial-Size Branching Programs Recognize Exactly Those Languages in '''NC'''<sup>1</sup>|url=http://www.cs.umass.edu/~barring/publications/bwbp.pdf|journal=J. Comput. Syst. Sci.|volume=38|pages=150–164|doi=10.1016/0022-0000(89)90037-8|issn=0022-0000|zbl=0667.68059|number=1}}</ref> стверджує, що '''BWBP'''&nbsp;— це точно нерозподілений '''NC'''<sup>1</sup>. Доведення теореми використовує нерозв'язність групи симетрії <math>S_{5}</math><ref name="CK50"/>.

=== Доказ теореми Баррінгтона ===
Доведемо, що розгалужену програму ('''РП''') зі сталою шириною і поліноміальним розміром можна перетворити на схему з '''NC'''<sup>1</sup>.

Від супротивного: нехай є схема '''C''' із '''NC'''<sup>1</sup>. Без обмеження загальності, вважатимемо, що в ній використовуються тільки [[Логічний вентиль|вентилі]] І і НЕ.

Визначення: РП називається такою, що <math>\sigma</math>-обчислює [[Булева функція|булеву функцію]] <math>f</math> або <math>(\sigma-f)</math>, якщо при <math>f = 0</math> вона дає результат&nbsp;— [[Перестановка|тотожну перестановку]], а при <math>f = 1</math> її результат&nbsp;— <math>\sigma</math>-перестановка. Оскільки наша схема '''C''' описує якусь булеву функцію <math>f</math> і тільки її, можемо взаємно замінювати ці терміни.

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

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

''Доведення'': оскільки <math>\sigma</math> і <math>\sigma^{-1}</math>&nbsp;— цикли, а будь-які два цикли є [[Клас спряженості|спряженими]], то існує така перестановка <math>\pi</math>, що <math>\sigma^{-1}</math> = <math>\pi\sigma\pi^{-1}</math>. Тоді домножимо на <math>\pi</math> перестановки <math>p_1</math> і <math>q_1</math> з першої інструкції РП зліва (щоб отримати перестановки <math>{\pi}p_1</math> і <math>{\pi}q_1</math>), а перестановки з останньої інструкції домножимо на <math>\pi^{-1}</math> справа (отримаємо <math>p_{n}\pi^{-1}</math> і <math>q_{n}\pi^{-1}</math>). Якщо до наших дій (без обмеження загальності) <math>{p_1}{p_2}...{p_n}</math> дорівнював <math>id</math>, то тепер результат буде <math>{\pi}id{\pi}^{-1} = id</math>, а якщо дорівнював <math>\sigma</math>, то результат дорівнює <math>\pi\sigma\pi^{-1} = \sigma^{-1}</math>. Так, ми отримали РП, що <math>\sigma^{-1}</math>-обчислює <math>f</math>, такої ж довжини (кількість інструкцій не змінилася).

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

'''Лема 2'''. Якщо є дві РП: що <math>\sigma</math>-обчислює <math>f</math> і <math>\gamma</math>-обчислює <math>t</math> з довжинами <math>l_1</math> і <math>l_2</math>, де <math>\sigma</math> і <math>\gamma</math>&nbsp;— 5-циклічні перестановки, то існує РП з 5-циклічною перестановкою <math>\varepsilon=\gamma\sigma\gamma^{-1}\sigma^{-1}</math> така, що РП <math>\varepsilon</math>-обчислює <math>f{\wedge}t</math>, і її розмір не перевищує <math>2(l_1</math> + <math>l_2)</math>.

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

<math></math>'''Доведення теореми'''

Доводитимемо за індукцією. Припустимо, що ми маємо схему ''C'' зі входами <math>x_1,...,x_n</math> і що для всіх підсхем ''D'' і 5-циклічних перестановок <math>\sigma</math> існує РП, що <math>\sigma</math>-обчислює ''D''. Покажемо, що для всіх 5-перестановок <math>\sigma</math> існує РП, що <math>\sigma</math>-обчислює ''C''.

* Якщо схема ''C'' видає <math>x_i</math>, то РП має одну інструкцію: перевірити значення <math>x_i</math> (0 або 1), і віддати <math>id</math> або <math>\sigma</math> (відповідно).
* Якщо схема ''C'' видає <math>\neg</math>''A'' для якоїсь іншої схеми ''A'', за приміткою до леми 1 створимо РП, що <math>\sigma</math>-обчислює <math>\neg</math>''A''.
* Якщо схема ''C'' видає ''A''<math>\wedge</math>''B'' для схем ''A'' і ''B'', створимо потрібну РП за лемою 2.

Розмір кінцевої розгалуженої програми не перевершує <math>4^d</math>, де <math>d</math>&nbsp;— глибина схеми. Якщо у схеми логарифмічна глибина, то в РП поліноміальна довжина.

== Примітки ==
<references group="" responsive="1"></references>

== Посилання ==

* {{Cite book
|title=Computational complexity. A modern approach
|last=Arora
|first=Sanjeev
|authorlink1=Санджив Арора
|last2=Barak
|first2=Boaz
|year=2009
|publisher=[[Cambridge University Press]]
|isbn=978-0-521-42426-4
|zbl=1193.68112
}}
* {{Cite book
|title=Boolean functions and computation models
|url=https://archive.org/details/booleanfunctions0000clot
|last=Clote
|first=Peter
|last2=Kranakis
|first2=Evangelos
|year=2002
|series=Texts in Theoretical Computer Science. An EATCS Series
|publisher=[[Springer-Verlag]]
|location=Berlin
|isbn=3-540-59436-1
|zbl=1016.94046
}}
* [http://www.cs.armstrong.edu/greenlaw/research/PARALLEL/limits.pdf Greenlaw, Raymond, James Hoover, and Walter Ruzzo. ''Limits To Parallel computation; P-Completeness Theory''.] {{Webarchive|url=https://web.archive.org/web/20130604010649/http://www.cs.armstrong.edu/greenlaw/research/PARALLEL/limits.pdf |date=4 Червня 2013 }} Архивная копия від 4 червня 2013 на Wayback Machine {{ISBN|0-19-508591-4}}
* {{Cite book
|title=The design and analysis of algorithms
|url=https://archive.org/details/designanalysisof0000koze
|last=Kozen
|first=Dexter C.
|authorlink1=Декстер Козен
|year=1992
}} Lectures 28&nbsp;— 34 and 36
* {{Cite book
|title=Theory of Computation
|url=https://archive.org/details/theoryofcomputat0000koze
|last=Kozen
|first=Dexter C.
|authorlink1=Декстер Козен
|year=2006
|series=Texts in Computer Science
|publisher=[[Springer-Verlag]]
|isbn=1-84628-297-7
|zbl=1102.68025
}} Lecture 12: Relation of ''NC'' to Time-Space Classes
* {{Cite book
|title=Computational Complexity
|last=Papadimitriou
|first=Christos
|authorlink1=Христос Пападімітріу
|year=1993
|publisher=Addison Wesley
|edition=1st
|pages=[https://archive.org/details/computationalcom00papa/page/n381 375]–381
|chapter=Section 15.3: The class '''NC'''
|isbn=0-201-53082-1
}}
* {{Cite book
|url=https://archive.org/details/finiteautomatafo0000stra
|title=Finite automata, formal logic, and circuit complexity
|last=Straubing
|first=Howard
|year=1994
|series=Progress in Theoretical Computer Science
|publisher=Birkhäuser
|location=Basel
|isbn=3-7643-3719-2
|zbl=0816.68086
}}
* {{Cite book
|title=Introduction to circuit complexity. A uniform approach
|last=Vollmer
|first=Heribert
|year=1998
|series=Texts in Theoretical Computer Science
|publisher=[[Springer-Verlag]]
|location=Berlin
|isbn=3-540-64310-9
|zbl=0931.68055
}}
{{Бібліоінформація}}
{{Класи складності}}
[[Категорія:Класи складності]]