В теорії складності обчислень класом NC (від англ. Nick’s Class) називають множину задач розв'язності, що розв'язуються за полілогарифмічний час на паралельному комп'ютері з поліноміальним числом процесорів. Іншими словами, задача належить до класу NC, якщо існують константи і такі, що її можна розв'язати за час при використанні паралельних процесорів. Стівен Кук назвав його «класом Ніка» на честь [en], який широко дослідив схеми з полілогарифмічною глибиною і поліноміальним розміром.
Так само, як клас P можна вважати класом податливих задач ([en]), так і NC можна вважати класом задач, які можна ефективно розв'язати на паралельному комп'ютері. NC — це підмножина P, тому що паралельні полілогарифмічні обчислення можна симулювати за допомогою послідовних поліноміальних обчислень. Невідомо, чи NP = P, але більшість учених вважає, що ні, з чого випливає, що найпевніше існують податливі задачі, які послідовні «від природи», і не можуть бути істотно прискореними за використання паралелізму. Так само, як клас NP-повних задач можна вважати класом «найпевніше непіддатливих» задач, так і клас [en], при зведенні до NC, можна вважати «найпевніше непаралелізовним» або «найпевніше послідовним від природи».
Паралельний комп'ютер у визначенні можна вважати паралельною машиною з довільним доступом (PRAM — від англ. parallel, random-access machine). Це паралельний комп'ютер із центральним пулом пам'яті, будь-який процесор якого може отримати доступ до будь-якого біта за сталий час. На визначення NC не впливає спосіб, за допомогою якого PRAM здійснює одночасний доступ декількох процесорів до одного біта.
NC можна визначити, як множину задач розв'язності, розв'язуваних [en] з полілогарифмічною глибиною і поліноміальним числом вентилів.
Задачі в NC
NC включає багато задач, зокрема:
- Додавання, множення і ділення цілих чисел;
- Множення матриць, підрахунок їх рангу, детермінанта, оберненої матриці;
- Поліноміальний НСД;
- Знаходження найбільшого парування.
Часто алгоритми для цих задач придумувалися окремо і не могли бути наївною адаптацією відомих алгоритмів — метод Гауса і алгоритм Евкліда покладаються на те, що операції виконуються послідовно.
Ієрархія NC
NCi — це множина задач розв'язності, розв'язуваних розподіленими булевими схемами з поліноміальною кількістю вентилів (з числом входів не більше двох) і глибиною , або розв'язуваних за час паралельним комп'ютером з поліноміальним числом процесорів. Очевидно,
що є NC-ієрархією.
Ми можемо пов'язати класи NC з класами пам'яті L, NL і :
Класи NC і AC однаково визначені, за винятком необмеженості кількості входів у вентилів для класу AC. Для кожного виконується:
Наслідком цього є NC = AC. Відомо, що обидва включення строгі для . Схожим чином можемо отримати, що NC еквівалентний множині задач, що розв'язуються на [en] з числом виборів на кожному кроці не більшим, ніж два, і з O(log n) пам'яті та альтераціями.
Нерозв'язана задача: чи є NC власним?
Одне з великих відкритих питань теорії складності обчислень — чи є власним кожне вкладення NC-ієрархії. Як зауважив Пападімітріу, якщо для якогось виконується NCi = NCi+1, то NCi = NCj для всіх , і, як наслідок, NCi = NC. Це спостереження називають згортанням NC-ієрархії, тому що навіть з однієї рівності в ланцюзі вкладень:
випливає, що вся NC-ієрархія «згортається» до якогось рівня . Таким чином, можливі два варіанти:
Поширена думка, що істинне саме (1), хоча поки не виявлено ніяких доказів щодо істинності того чи іншого твердження.
Теорема Баррінгтона
Розгалужена програма з змінними, шириною і довжиною складається з послідовності інструкцій довжини . Кожна інструкція — це трійка , де — це індекс змінної, яку потрібно перевірити , а і — це функції перестановки із в . Число називаються станами розгалуженої програми. Програма починається в стані 1, і кожна інструкція змінює стан на або , залежно від того, дорівнює -та змінна 0 чи 1.
Сімейство розгалужених програм складається з розгалужених програм з змінними для кожного .
Легко показати, що будь-яку мову на можна розпізнати сімейством розгалужених програм з шириною 5 і експоненціальною довжиною, або сімейством з експоненціальною шириною і лінійною довжиною.
Кожну регулярну мову на можна розпізнати сімейством розгалужених програм зі сталою шириною і лінійним числом інструкцій (оскільки ДСА можна перетворити на розгалужену програму). BWBP позначає клас мов, що розпізнаються сімейством розгалужених програм з обмеженою шириною і поліноміальною довжиною (англ. BWBP — branching programs of bounded width and polynomial length).
Теорема Баррінгтона стверджує, що BWBP — це точно нерозподілений NC1. Доведення теореми використовує нерозв'язність групи симетрії .
Доказ теореми Баррінгтона
Доведемо, що розгалужену програму (РП) зі сталою шириною і поліноміальним розміром можна перетворити на схему з NC1.
Від супротивного: нехай є схема C із NC1. Без обмеження загальності, вважатимемо, що в ній використовуються тільки вентилі І і НЕ.
Визначення: РП називається такою, що -обчислює булеву функцію або , якщо при вона дає результат — тотожну перестановку, а при її результат — -перестановка. Оскільки наша схема C описує якусь булеву функцію і тільки її, можемо взаємно замінювати ці терміни.
Для доведення використаємо дві леми:
Лема 1. Якщо є РП, що -обчислює , то існує і РП, що -обчислює (тобто, рівна при , і рівна при ).
Доведення: оскільки і — цикли, а будь-які два цикли є спряженими, то існує така перестановка , що = . Тоді домножимо на перестановки і з першої інструкції РП зліва (щоб отримати перестановки і ), а перестановки з останньої інструкції домножимо на справа (отримаємо і ). Якщо до наших дій (без обмеження загальності) дорівнював , то тепер результат буде , а якщо дорівнював , то результат дорівнює . Так, ми отримали РП, що -обчислює , такої ж довжини (кількість інструкцій не змінилася).
Примітка: якщо домножити вивід РП на справа, то очевидним чином отримаємо РП, що -обчислює функцію .
Лема 2. Якщо є дві РП: що -обчислює і -обчислює з довжинами і , де і — 5-циклічні перестановки, то існує РП з 5-циклічною перестановкою така, що РП -обчислює , і її розмір не перевищує + .
Доведення: викладемо «в ряд» інструкції чотирьох РП: , , , (будуємо зворотні за лемою 1). Якщо одна або обидві функції видають 0, то результат великої програми : наприклад, при . Якщо обидві функції видають 1, то . Тут , що істинне, оскільки ці перестановки 5-циклічні (через нерозв'язність групи симетрії ). Довжина нової РП обчислюється за визначенням.
Доведення теореми
Доводитимемо за індукцією. Припустимо, що ми маємо схему C зі входами і що для всіх підсхем D і 5-циклічних перестановок існує РП, що -обчислює D. Покажемо, що для всіх 5-перестановок існує РП, що -обчислює C.
- Якщо схема C видає , то РП має одну інструкцію: перевірити значення (0 або 1), і віддати або (відповідно).
- Якщо схема C видає A для якоїсь іншої схеми A, за приміткою до леми 1 створимо РП, що -обчислює A.
- Якщо схема C видає AB для схем A і B, створимо потрібну РП за лемою 2.
Розмір кінцевої розгалуженої програми не перевершує , де — глибина схеми. Якщо у схеми логарифмічна глибина, то в РП поліноміальна довжина.
Примітки
- Towards a complexity theory of synchronous parallel computation. D L'Enseignement mathematique 27 (англ.). Архів оригіналу за 10 Березня 2022. Процитовано 10 Березня 2022.
- Cook, Stephen A. (1 січня 1985). A taxonomy of problems with fast parallel algorithms. Information and Control. International Conference on Foundations of Computation Theory (англ.). 64 (1): 2—22. doi:10.1016/S0019-9958(85)80041-3. ISSN 0019-9958.
- Pippenger, Nicholas (1979). On simultaneous resource bounds. 20th Annual Symposium on Foundations of Computer Science (SFCS 1979) (English) : 307—311. doi:10.1109/SFCS.1979.29. ISSN 0272-5428.
- Arora & Barak (2009) p.120
- Arora & Barak (2009) p.118
- Papadimitriou (1994) Theorem 16.1
- Clote & Kranakis (2002) p.437
- Clote & Kranakis (2002) p.12
- S. Bellantoni and I. Oitavem (2004). Separating NC along the delta axis. Theoretical Computer Science. 318 (1–2): 57—78. doi:10.1016/j.tcs.2003.10.021.
- Clote & Kranakis (2002) p.50
- Barrington, David A. (1989). Bounded-Width Polynomial-Size Branching Programs Recognize Exactly Those Languages in NC1 (PDF). J. Comput. Syst. Sci. 38 (1): 150—164. doi:10.1016/0022-0000(89)90037-8. ISSN 0022-0000. Zbl 0667.68059.
Посилання
- ; Barak, Boaz (2009). Computational complexity. A modern approach. Cambridge University Press. ISBN . 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 . 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
- (1992). The design and analysis of algorithms. Lectures 28 — 34 and 36
- (2006). Theory of Computation. Texts in Computer Science. Springer-Verlag. ISBN . 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 .
- Straubing, Howard (1994). Finite automata, formal logic, and circuit complexity. Progress in Theoretical Computer Science. Basel: Birkhäuser. ISBN . Zbl 0816.68086.
- Vollmer, Heribert (1998). Introduction to circuit complexity. A uniform approach. Texts in Theoretical Computer Science. Berlin: Springer-Verlag. ISBN . Zbl 0931.68055.
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет
V teoriyi skladnosti obchislen klasom NC vid angl Nick s Class nazivayut mnozhinu zadach rozv yaznosti sho rozv yazuyutsya za polilogarifmichnij chas na paralelnomu komp yuteri z polinomialnim chislom procesoriv Inshimi slovami zadacha nalezhit do klasu NC yaksho isnuyut konstanti k displaystyle k i c displaystyle c taki sho yiyi mozhna rozv yazati za chas O log c n displaystyle O log c n pri vikoristanni O n k displaystyle O n k paralelnih procesoriv Stiven Kuk 1 2 nazvav jogo klasom Nika na chest Nika Pippenzhera en yakij shiroko doslidiv 3 shemi z polilogarifmichnoyu glibinoyu i polinomialnim rozmirom 4 Tak samo yak klas P mozhna vvazhati klasom podatlivih zadach teza Kobgema en tak i NC mozhna vvazhati klasom zadach yaki mozhna efektivno rozv yazati na paralelnomu komp yuteri 5 NC ce pidmnozhina P tomu sho paralelni polilogarifmichni obchislennya mozhna simulyuvati za dopomogoyu poslidovnih polinomialnih obchislen Nevidomo chi NP P ale bilshist uchenih vvazhaye sho ni z chogo viplivaye sho najpevnishe isnuyut podatlivi zadachi yaki poslidovni vid prirodi i ne mozhut buti istotno priskorenimi za vikoristannya paralelizmu Tak samo yak klas NP povnih zadach mozhna vvazhati klasom najpevnishe nepiddatlivih zadach tak i klas P povnih zadach en pri zvedenni do NC mozhna vvazhati najpevnishe neparalelizovnim abo najpevnishe poslidovnim vid prirodi Paralelnij komp yuter u viznachenni mozhna vvazhati paralelnoyu mashinoyu z dovilnim dostupom PRAM vid angl parallel random access machine Ce paralelnij komp yuter iz centralnim pulom pam yati bud yakij procesor yakogo mozhe otrimati dostup do bud yakogo bita za stalij chas Na viznachennya NC ne vplivaye sposib za dopomogoyu yakogo PRAM zdijsnyuye odnochasnij dostup dekilkoh procesoriv do odnogo bita NC mozhna viznachiti yak mnozhinu zadach rozv yaznosti rozv yazuvanih rozpodilenoyu bulevoyu shemoyu en z polilogarifmichnoyu glibinoyu i polinomialnim chislom ventiliv Zmist 1 Zadachi v NC 2 Iyerarhiya NC 2 1 Nerozv yazana zadacha chi ye NC vlasnim 3 Teorema Barringtona 3 1 Dokaz teoremi Barringtona 4 Primitki 5 PosilannyaZadachi v NCred NC vklyuchaye bagato zadach zokrema Dodavannya mnozhennya i dilennya cilih chisel Mnozhennya matric pidrahunok yih rangu determinanta obernenoyi matrici Polinomialnij NSD Znahodzhennya najbilshogo paruvannya Chasto algoritmi dlya cih zadach pridumuvalisya okremo i ne mogli buti nayivnoyu adaptaciyeyu vidomih algoritmiv metod Gausa i algoritm Evklida pokladayutsya na te sho operaciyi vikonuyutsya poslidovno Iyerarhiya NCred NCi ce mnozhina zadach rozv yaznosti rozv yazuvanih rozpodilenimi bulevimi shemami z polinomialnoyu kilkistyu ventiliv z chislom vhodiv ne bilshe dvoh i glibinoyu O log i n displaystyle O log i n nbsp abo rozv yazuvanih za chas O log i n displaystyle O log i n nbsp paralelnim komp yuterom z polinomialnim chislom procesoriv Ochevidno N C 1 N C 2 N C i N C displaystyle mathsf NC 1 subseteq mathsf NC 2 subseteq cdots subseteq mathsf NC i subseteq cdots mathsf NC nbsp sho ye NC iyerarhiyeyu Mi mozhemo pov yazati klasi NC z klasami pam yati L NL 6 i AC 7 N C 1 L N L A C 1 N C 2 P displaystyle mathsf NC 1 subseteq mathsf L subseteq mathsf NL subseteq mathsf AC 1 subseteq mathsf NC 2 subseteq mathsf P nbsp Klasi NC i AC odnakovo viznacheni za vinyatkom neobmezhenosti kilkosti vhodiv u ventiliv dlya klasu AC Dlya kozhnogo i displaystyle i nbsp vikonuyetsya 5 7 N C i A C i N C i 1 displaystyle mathsf NC i subseteq mathsf AC i subseteq mathsf NC i 1 nbsp Naslidkom cogo ye NC AC 8 Vidomo sho obidva vklyuchennya strogi dlya i 0 displaystyle i 0 nbsp 5 Shozhim chinom mozhemo otrimati sho NC ekvivalentnij mnozhini zadach sho rozv yazuyutsya na zminnij mashini Tyuringa en z chislom viboriv na kozhnomu kroci ne bilshim nizh dva i z O log n pam yati ta log n O 1 displaystyle log n O 1 nbsp alteraciyami 9 Nerozv yazana zadacha chi ye NC vlasnim red Odne z velikih vidkritih pitan teoriyi skladnosti obchislen chi ye vlasnim kozhne vkladennya NC iyerarhiyi Yak zauvazhiv Papadimitriu yaksho dlya yakogos i displaystyle i nbsp vikonuyetsya NCi NCi 1 to NCi NCj dlya vsih j i displaystyle j geqslant i nbsp i yak naslidok NCi NC Ce sposterezhennya nazivayut zgortannyam NC iyerarhiyi tomu sho navit z odniyeyi rivnosti v lancyuzi vkladen N C 1 N C 2 displaystyle mathsf NC 1 subseteq mathsf NC 2 subseteq cdots nbsp viplivaye sho vsya NC iyerarhiya zgortayetsya do yakogos rivnya i displaystyle i nbsp Takim chinom mozhlivi dva varianti N C 1 N C i N C i j N C displaystyle mathsf NC 1 subset cdots subset mathsf NC i subset cdots subset mathsf NC i j subset cdots mathsf NC nbsp N C 1 N C i N C i j N C displaystyle mathsf NC 1 subset cdots subset mathsf NC i cdots mathsf NC i j cdots mathsf NC nbsp Poshirena dumka sho istinne same 1 hocha poki ne viyavleno niyakih dokaziv shodo istinnosti togo chi inshogo tverdzhennya Teorema Barringtonared Rozgaluzhena programa z n displaystyle n nbsp zminnimi shirinoyu k displaystyle k nbsp i dovzhinoyu m displaystyle m nbsp skladayetsya z poslidovnosti instrukcij dovzhini m displaystyle m nbsp Kozhna instrukciya ce trijka i p q displaystyle i p q nbsp de i displaystyle i nbsp ce indeks zminnoyi yaku potribno pereviriti 1 i n displaystyle 1 leq i leq n nbsp a p displaystyle p nbsp i q displaystyle q nbsp ce funkciyi perestanovki iz 1 2 k displaystyle 1 2 k nbsp v 1 2 k displaystyle 1 2 k nbsp Chislo 1 2 k displaystyle 1 2 k nbsp nazivayutsya stanami rozgaluzhenoyi programi Programa pochinayetsya v stani 1 i kozhna instrukciya i p q displaystyle i p q nbsp zminyuye stan x displaystyle x nbsp na p x displaystyle p x nbsp abo q x displaystyle q x nbsp zalezhno vid togo dorivnyuye i displaystyle i nbsp ta zminna 0 chi 1 Simejstvo rozgaluzhenih program skladayetsya z rozgaluzhenih program z n displaystyle n nbsp zminnimi dlya kozhnogo n displaystyle n nbsp Legko pokazati sho bud yaku movu L displaystyle L nbsp na 0 1 displaystyle 0 1 nbsp mozhna rozpiznati simejstvom rozgaluzhenih program z shirinoyu 5 i eksponencialnoyu dovzhinoyu abo simejstvom z eksponencialnoyu shirinoyu i linijnoyu dovzhinoyu Kozhnu regulyarnu movu na 0 1 displaystyle 0 1 nbsp mozhna rozpiznati simejstvom rozgaluzhenih program zi staloyu shirinoyu i linijnim chislom instrukcij oskilki DSA mozhna peretvoriti na rozgaluzhenu programu BWBP poznachaye klas mov sho rozpiznayutsya simejstvom rozgaluzhenih program z obmezhenoyu shirinoyu i polinomialnoyu dovzhinoyu angl BWBP branching programs of bounded width and polynomial length 10 Teorema Barringtona 11 stverdzhuye sho BWBP ce tochno nerozpodilenij NC1 Dovedennya teoremi vikoristovuye nerozv yaznist grupi simetriyi S 5 displaystyle S 5 nbsp 10 Dokaz teoremi Barringtonared Dovedemo sho rozgaluzhenu programu RP zi staloyu shirinoyu i polinomialnim rozmirom mozhna peretvoriti na shemu z NC1 Vid suprotivnogo nehaj ye shema C iz NC1 Bez obmezhennya zagalnosti vvazhatimemo sho v nij vikoristovuyutsya tilki ventili I i NE Viznachennya RP nazivayetsya takoyu sho s displaystyle sigma nbsp obchislyuye bulevu funkciyu f displaystyle f nbsp abo s f displaystyle sigma f nbsp yaksho pri f 0 displaystyle f 0 nbsp vona daye rezultat totozhnu perestanovku a pri f 1 displaystyle f 1 nbsp yiyi rezultat s displaystyle sigma nbsp perestanovka Oskilki nasha shema C opisuye yakus bulevu funkciyu f displaystyle f nbsp i tilki yiyi mozhemo vzayemno zaminyuvati ci termini Dlya dovedennya vikoristayemo dvi lemi Lema 1 Yaksho ye RP sho s displaystyle sigma nbsp obchislyuye f displaystyle f nbsp to isnuye i RP sho s 1 displaystyle sigma 1 nbsp obchislyuye f displaystyle f nbsp tobto rivna i d displaystyle id nbsp pri f 0 displaystyle f 0 nbsp i rivna s 1 displaystyle sigma 1 nbsp pri f 1 displaystyle f 1 nbsp Dovedennya oskilki s displaystyle sigma nbsp i s 1 displaystyle sigma 1 nbsp cikli a bud yaki dva cikli ye spryazhenimi to isnuye taka perestanovka p displaystyle pi nbsp sho s 1 displaystyle sigma 1 nbsp p s p 1 displaystyle pi sigma pi 1 nbsp Todi domnozhimo na p displaystyle pi nbsp perestanovki p 1 displaystyle p 1 nbsp i q 1 displaystyle q 1 nbsp z pershoyi instrukciyi RP zliva shob otrimati perestanovki p p 1 displaystyle pi p 1 nbsp i p q 1 displaystyle pi q 1 nbsp a perestanovki z ostannoyi instrukciyi domnozhimo na p 1 displaystyle pi 1 nbsp sprava otrimayemo p n p 1 displaystyle p n pi 1 nbsp i q n p 1 displaystyle q n pi 1 nbsp Yaksho do nashih dij bez obmezhennya zagalnosti p 1 p 2 p n displaystyle p 1 p 2 p n nbsp dorivnyuvav i d displaystyle id nbsp to teper rezultat bude p i d p 1 i d displaystyle pi id pi 1 id nbsp a yaksho dorivnyuvav s displaystyle sigma nbsp to rezultat dorivnyuye p s p 1 s 1 displaystyle pi sigma pi 1 sigma 1 nbsp Tak mi otrimali RP sho s 1 displaystyle sigma 1 nbsp obchislyuye f displaystyle f nbsp takoyi zh dovzhini kilkist instrukcij ne zminilasya Primitka yaksho domnozhiti vivid RP s 1 f displaystyle sigma 1 f nbsp na s displaystyle sigma nbsp sprava to ochevidnim chinom otrimayemo RP sho s displaystyle sigma nbsp obchislyuye funkciyu f displaystyle neg f nbsp Lema 2 Yaksho ye dvi RP sho s displaystyle sigma nbsp obchislyuye f displaystyle f nbsp i g displaystyle gamma nbsp obchislyuye t displaystyle t nbsp z dovzhinami l 1 displaystyle l 1 nbsp i l 2 displaystyle l 2 nbsp de s displaystyle sigma nbsp i g displaystyle gamma nbsp 5 ciklichni perestanovki to isnuye RP z 5 ciklichnoyu perestanovkoyu e g s g 1 s 1 displaystyle varepsilon gamma sigma gamma 1 sigma 1 nbsp taka sho RP e displaystyle varepsilon nbsp obchislyuye f t displaystyle f wedge t nbsp i yiyi rozmir ne perevishuye 2 l 1 displaystyle 2 l 1 nbsp l 2 displaystyle l 2 nbsp Dovedennya viklademo v ryad instrukciyi chotiroh RP g t displaystyle gamma t nbsp s f displaystyle sigma f nbsp g 1 t displaystyle gamma 1 t nbsp s 1 f displaystyle sigma 1 f nbsp buduyemo zvorotni za lemoyu 1 Yaksho odna abo obidvi funkciyi vidayut 0 to rezultat velikoyi programi e i d displaystyle varepsilon id nbsp napriklad pri f 0 t 1 e i d s i d s 1 i d displaystyle f 0 t 1 varepsilon id sigma id sigma 1 id nbsp Yaksho obidvi funkciyi vidayut 1 to e g s g 1 s 1 displaystyle varepsilon gamma sigma gamma 1 sigma 1 nbsp Tut g s g 1 s 1 i d lt gt g s s g displaystyle gamma sigma gamma 1 sigma 1 neq id lt gt gamma sigma neq sigma gamma nbsp sho istinne oskilki ci perestanovki 5 ciklichni cherez nerozv yaznist grupi simetriyi S 5 displaystyle S 5 nbsp Dovzhina novoyi RP obchislyuyetsya za viznachennyam displaystyle Dovedennya teoremi Dovoditimemo za indukciyeyu Pripustimo sho mi mayemo shemu C zi vhodami x 1 x n displaystyle x 1 x n nbsp i sho dlya vsih pidshem D i 5 ciklichnih perestanovok s displaystyle sigma nbsp isnuye RP sho s displaystyle sigma nbsp obchislyuye D Pokazhemo sho dlya vsih 5 perestanovok s displaystyle sigma nbsp isnuye RP sho s displaystyle sigma nbsp obchislyuye C Yaksho shema C vidaye x i displaystyle x i nbsp to RP maye odnu instrukciyu pereviriti znachennya x i displaystyle x i nbsp 0 abo 1 i viddati i d displaystyle id nbsp abo s displaystyle sigma nbsp vidpovidno Yaksho shema C vidaye displaystyle neg nbsp A dlya yakoyis inshoyi shemi A za primitkoyu do lemi 1 stvorimo RP sho s displaystyle sigma nbsp obchislyuye displaystyle neg nbsp A Yaksho shema C vidaye A displaystyle wedge nbsp B dlya shem A i B stvorimo potribnu RP za lemoyu 2 Rozmir kincevoyi rozgaluzhenoyi programi ne perevershuye 4 d displaystyle 4 d nbsp de d displaystyle d nbsp glibina shemi Yaksho u shemi logarifmichna glibina to v RP polinomialna dovzhina Primitkired Towards a complexity theory of synchronous parallel computation D L Enseignement mathematique 27 angl Arhiv originalu za 10 Bereznya 2022 Procitovano 10 Bereznya 2022 Cook Stephen A 1 sichnya 1985 A taxonomy of problems with fast parallel algorithms Information and Control International Conference on Foundations of Computation Theory angl 64 1 2 22 doi 10 1016 S0019 9958 85 80041 3 ISSN 0019 9958 Pippenger Nicholas 1979 On simultaneous resource bounds 20th Annual Symposium on Foundations of Computer Science SFCS 1979 English 307 311 doi 10 1109 SFCS 1979 29 ISSN 0272 5428 Arora amp Barak 2009 p 120 a b v Arora amp Barak 2009 p 118 Papadimitriou 1994 Theorem 16 1 a b Clote amp Kranakis 2002 p 437 Clote amp Kranakis 2002 p 12 S Bellantoni and I Oitavem 2004 Separating NC along the delta axis Theoretical Computer Science 318 1 2 57 78 doi 10 1016 j tcs 2003 10 021 a b Clote amp Kranakis 2002 p 50 Barrington David A 1989 Bounded Width Polynomial Size Branching Programs Recognize Exactly Those Languages in NC1 PDF J Comput Syst Sci 38 1 150 164 doi 10 1016 0022 0000 89 90037 8 ISSN 0022 0000 Zbl 0667 68059 Posilannyared 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 Arhivovano 4 Chervnya 2013 u Wayback Machine Arhivnaya kopiya vid 4 chervnya 2013 na 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 vid 1st Addison Wesley s 375 381 ISBN 0 201 53082 1 Straubing Howard 1994 Finite automata formal logic and circuit complexity Progress in Theoretical Computer Science Basel Birkhauser 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 Otrimano z https uk wikipedia org w index php title Klas skladnosti NC amp oldid 43200063