Параллельдік есептеулер классы: NC және оның сипаттамасы

Кіріспе

Есептеу күрделілігі теориясында NC класы ("Ник класы") – полиномиалдық сандағы процессорлары бар параллель компьютерде полилогарифмдік уақытта шешілетін шешімдік есептердің жиыны. Яғни, кіріс өлшемі n болатын есеп, егер c және k тұрақтылары болса, [[Big O notation]] параллельді процессорларды қолдану арқылы [[Big O notation]] уақытында шешіле алатын болса, NC класына жатады. Стивен Кук "Ник класы" атауын Ник Пиппенгердің құрметіне атады, ол полилогарифмдік тереңдігі және полиномиалдық өлшемі бар схемалар туралы кең ауқымды зерттеулер жүргізген. P класын (Кобхэмнің тезисі) шешуге болатын есептер деп қарастырылатындай, NC класын параллель компьютерде тиімді шешілетін есептер деп қарастыруға болады. NC, P класының ішкі жиыны, себебі полилогарифмдік параллель есептеулерді полиномиалдық уақыттық реттік есептеулермен модельдеуге болады. NC = P екендігі әлі белгісіз, бірақ көптеген зерттеушілер бұл теріс деп күдіктенеді, яғни параллелизмді қолдану арқылы елеулі түрде жылдамдатылмауы мүмкін, "табиғатынан реттік" кейбір есептер бар. NP-толық класты "көп жағдайда шешілмейтін" деп қарастырылатындай, NC азайтуларын қолданғанда, P-толық класты "көп жағдайда параллельдеуге келмейтін" немесе "табиғатынан реттік" деп қарастыруға болады. Анықтамадағы параллель компьютерді параллельді, кездейсоқ кіру машинасы (PRAM) деп қарастыруға болады. Яғни, орталық жадқа ие параллель компьютер, онда кез келген процессор кез келген жад битіне тұрақты уақытта кіре алады. NC анықтамасы PRAM бір бітке бірден бір процессордың кіруін қалай басқаратынына тәуелді емес. Ол CRCW, CREW немесе EREW түрінде болуы мүмкін. Бұл модельдердің сипаттамалары PRAM мақаласында келтірілген. Балама ретінде, NC класын біркелкі Бульдік схемамен шешілетін шешімдік есептер ретінде анықтауға болады (оны кіріс ұзындығынан есептеуге болады, NC үшін кіріс өлшемі n болғанда n-нің логарифмдік кеңістігінде Бульдік схеманы есептей аламыз деп есептейміз) полилогарифмдік тереңдігі және 2-ге дейінгі максималды желдеткіші бар қақпалардың полиномиалдық санымен. RNC класы – бұл кездейсоқтыққа қол жеткізу мүмкіндігі бар NC класын кеңейтетін класс.

In computational complexity theory, the class NC (for "Nick's Class") is the set of decision problems decidable in polylogarithmic time on a parallel computer with a polynomial number of processors. In other words, a problem with input size n is in NC if there exist constants c and k such that it can be solved in time [[Big O notation using [[Big O notation parallel processors. Stephen Cook coined the name "Nick's class" after Nick Pippenger, who had done extensive research on circuits with polylogarithmic depth and polynomial size. Just as the class P can be thought of as the tractable problems (Cobham's thesis), so NC can be thought of as the problems that can be efficiently solved on a parallel computer. NC is a subset of P because polylogarithmic parallel computations can be simulated by polynomial time sequential ones. It is unknown whether NC = P, but most researchers suspect this to be false, meaning that there are probably some tractable problems that are "inherently sequential" and cannot significantly be sped up by using parallelism. Just as the class NP complete can be thought of as "probably intractable", so the class P complete, when using NC reductions, can be thought of as "probably not parallelizable" or "probably inherently sequential". The parallel computer in the definition can be assumed to be a parallel, random access machine (PRAM). That is a parallel computer with a central pool of memory, and any processor can access any bit of memory in constant time. The definition of NC is not affected by the choice of how the PRAM handles simultaneous access to a single bit by more than one processor. It can be CRCW, CREW, or EREW. See PRAM for descriptions of those models. Equivalently, NC can be defined as those decision problems decidable by a uniform Boolean circuit (which can be calculated from the length of the input, for NC, we suppose we can compute the Boolean circuit of size n in logarithmic space in n) with polylogarithmic depth and a polynomial number of gates with a maximum fan in of 2. RNC is a class extending NC with access to randomness.

Мысал

NC1 проблемасының мысалы – бит тізбегіндегі теңдік тексеруі. Мәселе 1 және 0-ден тұратын тізбектегі 1-лер санын санаудан тұрады. Оңай шешім – тізбектің барлық биттерін қосу. Қосу ассоциативті екендігіне байланысты, осы қасиетті рекурсивті қолдану арқылы ұзындығы бар екілік ағаш құруға болады, онда екі бит арасындағы әрбір қосынды және негізгі логикалық операторлар арқылы, мысалы, бульдік өрнек арқылы өрнектеледі.

ҰК иерархиясы

NCi – ең көп дегенде екі кірісі және O((log n)^i) тереңдігі бар полиномиялық саны қақпалары бар біртекті бульдік схемалармен шешілетін шешімдер класы, немесе полиномиялық саны бар процессорлары бар параллельді компьютерде O((log n)^i) уақытында шешілетін шешімдер класы. Әрине, бізде

NC иерархиясын құрайтын қатарлар бар. Біз NC кластарын L, NL және AC кеңістік кластарымен байланыстыра аламыз. NC кластары AC кластарымен ұқсас, бірақ қақпалары шексіз таралуға ие. Кез келген i үшін екі кіріктіру де i = 0 үшін қатаң екені белгілі.

Ашық мәселе: NC дұрыс па?

Күрделілік теориясындағы маңызды ашық мәселе – NC иерархиясындағы әрбір кіріктірудің дұрыс екені немесе емесі. Пападимитриудың байқауы бойынша, егер NCi = NCi+1 болса, кейбір i үшін, онда NCi = NCj болады, барлық j ≥ i үшін, соның салдарынан NCi = NC. Бұл байқау NC иерархиясының құлдырауы деп аталады, себебі кіріктіру тізбегіндегі жалғыз теңдік те бүкіл NC иерархиясының қандай да бір деңгейге дейін "құлдырауына" алып келеді. Осылайша, екі мүмкіндік бар:

Көпшілік (1) дұрыс деп санайды, бірақ екі жағдайдың да шындығын растайтын дәлел әлі табылмаған.

NC0

NC0 арнайы класы тек тұрақты ұзындығы бар кіріс биттерімен жұмыс істейді. Сондықтан ол біркелкі логикалық схемалармен анықталатын, тұрақты тереңдігі және шектелген кіріс саны бар функциялар класы ретінде сипатталады.

Баррингтон теоремасы

Тармақталу бағдарламасы, n айнымалысы, k ені және m ұзындығы бар болса, m нұсқаудан тұрады. Әрбір нұсқау (i, p, q) түрінде болады, мұнда i – тексеруге арналған айнымалының индексі (1 ≤ i ≤ n), ал p және q – {1, 2, ..., k} жиынынан {1, 2, ..., k} жиынына дейінгі функциялар. 1, 2, ..., k сандары тармақталу бағдарламасының күйлері деп аталады. Бағдарлама бастапқыда 1-ші күйде басталады, әрбір нұсқау (i, p, q) i-ші айнымалы 0 немесе 1 болған жағдайда күйді x-тен p(x) немесе q(x) күйіне өзгертеді. Кірісті бағдарламаның соңғы күйіне бейімдейтін функция бағдарламаның нәтижесі деп аталады (нақтырақ айтқанда, кірістің нәтижесі – кез келген бастапқы күйді тиісті соңғы күйге бейімдейтін функция). Егер функциялар жиынтығы болса және айнымалы тізбегі A-да болса, оның нәтижесі F-де болады, онда бағдарлама айнымалы мәндердің жиынтығын қабылдайды. Тармақталу бағдарламаларының отбасы – әр n үшін n айнымалысы бар тармақталу бағдарламасы. Ол тілді қабылдайды, егер n айнымалы бағдарламасы n ұзындығындағы кірістерге шектелген тілді қабылдаса. {0,1} жиынындағы кез келген L тілін 5 ені және экспоненциалды ұзындығы бар немесе экспоненциалды ені және сызықтық ұзындығы бар тармақталу бағдарламаларының отбасымен тануға болады. {0,1} жиынындағы кез келген реттелген тілді тұрақты ені және нұсқаулардың сызықтық саны бар тармақталу бағдарламаларының отбасы тани алады (өйткені автомат DFA тармақталу бағдарламасына түрлендіріледі). BWBP – шектелген ені және полиномдық ұзындығы бар тармақталу бағдарламаларының отбасымен танылатын тілдер класын білдіреді. Баррингтон теоремасы BWBP – дәл біркелкі емес NC1 дейді. Дәлелдеуде S5 симметриялық тобының шешілмейтіні қолданылады. Теорема өте таңқаларлық. Мысалы, көпшілік функциясын тұрақты ені және полиномдық мөлшері бар тармақталу бағдарламаларының отбасы арқылы есептеуге болады, ал интуиция полиномдық мөлшерге жету үшін сызықтық сандық күйлер қажет деп болжауы мүмкін.

Баррингтон теоремасының дәлелі

Тұрақты ені және полиномдық өлшемі бар тармақталу бағдарламасын NC1 схемасына оңай (бөліп-жеңу арқылы) түрлендіруге болады. Керісінше, егер NC1 схемасы берілген болсын. Жалпылықты жоғалтпай, ол тек ЖӘНЕ және ЖОҚ есіктерін ғана қолданады деп есептейік. Егер схеманың шығысы 0 болса, сәйкестік ретінде, ал шығысы 1 болса, схеманы есептейтін тармақталу бағдарламасын α деп атаймыз. 1-лема және барлық 5 ұзындықтағы циклдар бірімен-бірі байланысты екендігінің салдары ретінде, кез келген екі 5 цикл үшін , , егер C схемасын есептейтін α тармақталу бағдарламасы болса, онда C схемасын есептейтін β тармақталу бағдарламасы да болады, олардың ұзындығы бірдей. Тармақталу бағдарламасының өлшемі d схемасының тереңдігі болғанда 4-тен аспайды. Егер схеманың тереңдігі логарифмдік болса, тармақталу бағдарламасы полиномдық ұзындыққа ие болады.