Кіріспе
Компьютерлік күрделілік теориясының кездейсоқ полиномиялық уақыт класы
Компьютерлік күрделілік теориясында кездейсоқ полиномиялық уақыт (RP) – бұл мына қасиеттері бар ықтималдық Тьюринг машинасы бар проблемалардың күрделілік класы:
RP алгоритмі (1 рет іске қосылғанда) ≥ 1/2 ≤ 1/2 0 1RP алгоритмі (n рет іске қосылғанда) ≥ 1 − 2−n ≤ 2−n 0 1co RP алгоритмі (1 рет іске қосылғанда) 1 0 ≤ 1/2 ≥ 1/2
Ол кірістің өлшеміне қатысты полиномиялық уақытта жұмыс істейді.
Егер дұрыс жауап «ЖОҚ» болса, ол әрқашан «ЖОҚ» деп қайтарады.
Егер дұрыс жауап «ИӘ» болса, онда ол кем дегенде 1/2 ықтималдықпен «ИӘ» деп қайтарады (әйтпесе, «ЖОҚ» деп қайтарады). Яғни, алгоритм жұмыс істеп тұрғанда толығымен кездейсоқ монетаны лақтыруға рұқсат етіледі. Алгоритм «ИӘ» деп қайтара алатын жалғыз жағдай – нақты жауап «ИӘ» болғанда ғана; сондықтан, егер алгоритм аяқталып, «ИӘ» деп шығарса, онда дұрыс жауап міндетті түрде «ИӘ» болады; алайда, алгоритм нақты жауаптан тәуелсіз «ЖОҚ» деп аяқталуы мүмкін. Демек, егер алгоритм «ЖОҚ» деп қайтарса, ол қате болуы мүмкін. Кейбір авторлар бұл класты R деп атайды, бірақ бұл атау көбінесе рекурсивті тілдер класы үшін қолданылады. Егер дұрыс жауап «ИӘ» болса және алгоритм n рет іске қосылса, әр іске қосылу нәтижесі статистикалық тұрғыдан бір-бірінен тәуелсіз болса, онда ол кем дегенде 1 − 2−n ықтималдығымен кем дегенде бір рет «ИӘ» деп қайтарады. Егер алгоритм 100 рет іске қосылса, онда оның әр жолы дұрыс емес жауап беру ықтималдығы, алгоритмді іске қосатын компьютердің жадысындағы ғарыштық сәулелердің бұзуынан төмен болады. Осы мағынада, егер кездейсоқ сандар көзі қолжетімді болса, RP-дегі көптеген алгоритмдер өте практикалық. Анықтамадағы 1/2 саны кездейсоқ. RP жиынында дәл сол мәселелер болады, тіпті егер 1/2 кез-келген тұрақты, нөлден өзгеше ықтималдықпен ауыстырылса да; мұнда тұрақты – алгоритмге берілген кірістен тәуелсіз дегенді білдіреді.
In computational complexity theory, randomized polynomial time (RP) is the complexity class of problems for which a probabilistic Turing machine exists with these properties:
RP algorithm (1 run) ≥ 1/2 ≤ 1/2 0 1RP algorithm (n runs) ≥ 1 − 2−n ≤ 2−n 0 1co RP algorithm (1 run) 1 0 ≤ 1/2 ≥ 1/2
It always runs in polynomial time in the input size
If the correct answer is NO, it always returns NO
If the correct answer is YES, then it returns YES with probability at least 1/2 (otherwise, it returns NO). In other words, the algorithm is allowed to flip a truly random coin while it is running. The only case in which the algorithm can return YES is if the actual answer is YES; therefore if the algorithm terminates and produces YES, then the correct answer is definitely YES; however, the algorithm can terminate with NO regardless of the actual answer. That is, if the algorithm returns NO, it might be wrong. Some authors call this class R, although this name is more commonly used for the class of recursive languages. If the correct answer is YES and the algorithm is run n times with the result of each run statistically independent of the others, then it will return YES at least once with probability at least 1 − 2^(−n). So if the algorithm is run 100 times, then the chance of it giving the wrong answer every time is lower than the chance that cosmic rays corrupted the memory of the computer running the algorithm. In this sense, if a source of random numbers is available, most algorithms in RP are highly practical. The fraction 1/2 in the definition is arbitrary. The set RP will contain exactly the same problems, even if the 1/2 is replaced by any constant nonzero probability less than 1; here constant means independent of the input to the algorithm.
Қатысушы күрделілік сыныптары
RP анықтамасы "Иә" жауабы әрқашан дұрыс, ал "Жоқ" жауабы қате болуы мүмкін дейді, себебі "Иә" мысалы "Жоқ" жауабын беруі мүмкін. Күрделілік класы co RP – мұның керісі, онда "Иә" жауабы қате болуы мүмкін, ал "Жоқ" жауабы әрқашан дұрыс. BPP класы "Иә" және "Жоқ" мысалдары үшін де қате жауап бере алатын алгоритмдерді сипаттайды, сондықтан ол RP және co RP кластарын қамтиды. RP және co RP жиындарының қиылысы ZPP деп аталады. RP-ні R деп атауға болатындай, кейбір авторлар co RP-ні co R деп атайды.
P және NP-ге қосылу
P - RP жиынтығының кіші жиынтығы, ал RP - NP жиынтығының кіші жиынтығы. Сол сияқты, P - co RP жиынтығының кіші жиынтығы, ал co RP - co NP жиынтығының кіші жиынтығы. Бұл кіші жиынтықтардың қатаң екендігі белгісіз. Дегенмен, егер P = BPP деген кең таралған болжам дұрыс болса, онда RP, co RP және P жиынтықтары бірігеді (барлығы тең болады). Сонымен қатар, егер P ≠ NP деп есептесек, онда RP жиынтығы NP жиынтығына қатаң түрде кіріктірілген болады. RP = co RP екендігі немесе RP жиынтығы NP және co NP жиынтықтарының қиылысының кіші жиынтығы екендігі белгісіз, бірақ бұл P = BPP болған жағдайда орын алады. P жиынтығында, қазіргі уақытта RP жиынтығына жататын, бірақ P жиынтығына жататыны белгісіз проблеманың нақты мысалы – полиномдық сәйкестік тексеру, яғни берілген көп айнымалы арифметикалық өрнектің бүтін сандар бойынша нөлдік полином екенін анықтау мәселесі. Мысалы, x·x − y·y − (x + y)·(x − y) нөлдік полином, ал x·x + y·y – емес. RP жиынтығын сипаттаудың кейде қолдануға ыңғайлырақ баламалы жолы – нон-детерминистік Тьюринг машиналарын қолданатын проблемалар жиынтығы, онда машина егер және тек егер есептеу жолдарының кем дегенде тұрақты үлесі, кіріс мөлшеріне тәуелсіз болса, қабылданады. Ал NP жиынтығына керісінше, тек бір қабылданатын жол жеткілікті, ол жолдардың экспоненциалды түрде кішкентай бөлігін құрауы мүмкін. Осы сипаттама RP жиынтығының NP жиынтығының кіші жиынтығы екенін анық көрсетеді.
x·x + y·y is not. An alternative characterization of RP that is sometimes easier to use is the set of problems recognizable by nondeterministic Turing machines where the machine accepts if and only if at least some constant fraction of the computation paths, independent of the input size, accept. NP on the other hand, needs only one accepting path, which could constitute an exponentially small fraction of the paths. This characterization makes the fact that RP is a subset of NP obvious.