Кіріспе
Есептеу күрделілігі теориясында, шешім проблемасы P-толық (P күрделілік класы үшін толық) деп аталады, егер ол P класында болса және P класындағы әрбір проблема тиісті азайту арқылы оған дейін келтіріле алады. P-толық шешім проблемаларының түсінігі мыналарды талдау үшін пайдалы:
қай проблемаларды тиімді түрде параллельдеу қиын,
қай проблемаларды шектеулі кеңістікте шешу қиын. Атап айтқанда, полиномиалдық уақыт азайтудан күштірек азайту түрлері қарастырылғанда. Қолданылатын азайтудың нақты түрі әртүрлі болуы мүмкін және нақты проблемалар жиынтығына әсер етуі мүмкін. Жалпы, полиномиалдық уақыт азайтудан күштірек азайтулар қолданылады, өйткені P класындағы барлық тілдер (бос тіл мен барлық жолдардың тілінен басқа) полиномиалдық уақыт азайтулары бойынша P-толық болып табылады. Егер біз NC азайтуларын қолдансақ, яғни процессорлардың полиномиалдық саны бар параллель компьютерде полилогарифмдік уақытта жұмыс істей алатын азайтуларды, онда барлық P-толық проблемалары NC класынан тыс жатады және сондықтан NC ≠ P деген дәлелденбеген болжам бойынша тиімді параллельдестірілмейді. Егер біз күшті логарифмдік кеңістік азайтуын қолдансақ, бұл рас болып қалады, бірақ сонымен қатар барлық P-толық проблемалары L класынан тыс жатады дегенге келеміз, L ≠ P деген әлсіз дәлелденбеген болжам бойынша. Бұл жағдайда P-толық жиын кішірек болуы мүмкін.
which problems are difficult to solve in limited space. specifically when stronger notions of reducibility than polytime reducibility are considered. The specific type of reduction used varies and may affect the exact set of problems. Generically, reductions stronger than polynomial time reductions are used, since all languages in P (except the empty language and the language of all strings) are P complete under polynomial time reductions. If we use NC reductions, that is, reductions which can operate in polylogarithmic time on a parallel computer with a polynomial number of processors, then all P complete problems lie outside NC and so cannot be effectively parallelized, under the unproven assumption that NC ≠ P. If we use the stronger log space reduction, this remains true, but additionally we learn that all P complete problems lie outside L under the weaker unproven assumption that L ≠ P. In this latter case the set P complete may be smaller.
Мотивация
P класы, әдетте, ретті компьютер үшін барлық "шешілетін" мәселелерді қамтиды, ал NC класы параллель компьютерде тиімді шешілетін мәселелерден тұрады. Өйткені, параллель компьютерлерді ретті машинада модельдеуге болады. NC = P екендігі белгісіз. Басқаша айтқанда, өзінен-өзі реттілікке ие болатын шешілетін мәселелер бар-жоғы белгісіз. P, NP-ге тең емес деп күдікті болғаны сияқты, NC да P-ге тең емес деп күдікті. Сол сияқты, L класы логарифмдік кеңістікте ретті компьютермен шешілетін барлық мәселелерді қамтиды. Мұндай машиналар полиномиалдық уақытта жұмыс істейді, өйткені олар полиномиалдық саны конфигурацияға ие болуы мүмкін. L ≠ P деп күдікті; яғни, полиномиалдық уақытта шешілетін кейбір мәселелер логарифмдік кеңістіктен артық ресурстарды қажет етеді. P = NP сұрағын талдау үшін NP-толық проблемаларды пайдалану сияқты, "параллелдеуге келмейтін" немесе "өзінен-өзі реттілікке ие" проблемалар ретінде қаралатын P-толық проблемалары NC = P сұрағын зерттеуде ұқсас рөл атқарады. P-толық проблеманың шешімін параллельдеудің тиімді тәсілін табу NC = P екенін көрсетеді. Оны "суперлогарифмдік кеңістік қажет ететін проблемалар" деп те қарастыруға болады; P-толық проблеманың логарифмдік кеңістіктегі шешімі (логарифмдік кеңістікте азайтуға негізделген анықтаманы қолдану) L = P екенін білдіреді. Бұған негізделген логика, NP-толық проблеманың полиномиалдық уақыттағы шешімінің P = NP екенін дәлелдейтін логикаға ұқсас: егер P-дегі кез келген проблемадан A проблемасына NC азайту және A үшін NC шешімі болса, онда NC = P. Сол сияқты, егер P-дегі кез келген проблемадан A проблемасына логарифмдік кеңістікте азайту және A үшін логарифмдік кеңістікте шешім болса, онда L = P.
Similarly, the class L contains all problems that can be solved by a sequential computer in logarithmic space. Such machines run in polynomial time because they can have a polynomial number of configurations. It is suspected that L ≠ P; that is, that some problems that can be solved in polynomial time also require more than logarithmic space. Similarly to the use of NP complete problems to analyze the P = NP question, the P complete problems, viewed as the "probably not parallelizable" or "probably inherently sequential" problems, serves in a similar manner to study the NC = P question. Finding an efficient way to parallelize the solution to some P complete problem would show that NC = P. It can also be thought of as the "problems requiring superlogarithmic space"; a log space solution to a P complete problem (using the definition based on log space reductions) would imply L = P.
The logic behind this is analogous to the logic that a polynomial time solution to an NP complete problem would prove P = NP: if we have a NC reduction from any problem in P to a problem A, and an NC solution for A, then NC = P. Similarly, if we have a log space reduction from any problem in P to a problem A, and a log space solution for A, then L = P.
P-толық деп танылмаған проблемалар
Кейбір NP проблемаларының NP-толық немесе P класына жататыны белгісіз. Бұл проблемалар (мысалы, көбейткіштерге жіктеу, граф изоморфизмі, паритеттік ойындар) қиын деп саналады. Сол сияқты, P класында P-толық немесе NC класына жататыны белгісіз, бірақ параллель өңдеуге қиын деп есептелетін мәселелер де бар. Мысалға, екі санның ең үлкен ортақ бөлгішін табу, екі сан берілген кезде кеңейтілген Евклид алгоритмінің қандай нәтиже беретінін анықтау және үлкен бүтін сандық салмақтары бар графтың максималды салмақты сәйкестігін есептеу сияқты шешім есептерінің түрлерін келтіруге болады.