Кездейсоқ Логарифмдік Кеңістік және Есептеу Қаттылығы Сыныптары
RL (complexity)
RL (Randomized Logarithmic space): Есептерді шешу үшін логарифмдік кеңістік пен полиномдық уақыт қолданатын, бір жақты қателікке жол беретін алгоритмдер класы. Компьютерлік теория.
Ағылшыншамен салыстырыңыз: абзацты басыңыз — түпнұсқа терезеде ашылады. Абзац астындағы EN түймесі оны мәтін ішінде көрсетеді.
Мазмұны
Кіріспе
Рандомизацияланған логарифмдік кеңістік (RL), кейде RLP (Randomized Logarithmic space Polynomial time) деп аталады, – бұл есептеу күрделілігі теориясының күрделік класы. Ол бір жақты қателігі бар ықтималдық Тьюринг машиналарымен логарифмдік кеңістікте және полиномдық уақытта шешілетін мәселелерді қамтиды. Ол RP класына ұқсас, бірақ логарифмдік кеңістікке шектеу қоймайды.
Randomized Logarithmic space (RL), sometimes called RLP (Randomized Logarithmic space Polynomial time), is the complexity class of computational complexity theory problems solvable in logarithmic space and polynomial time with probabilistic Turing machines with one sided error. It is named in analogy with RP, which is similar but has no logarithmic space restriction.
Анықтама
РЛ анықтамасындағы ықтималдық Тьюринг машиналары ешқашан дұрыс жауап бермейді, бірақ 1/3 уақыттан кемінде дұрыс емес жауап беруге рұқсат етіледі; бұл бір жақты қате деп аталады. 1/3 тұрақтысы кездейсоқ; 0 < x < 1 шартын қанағаттандыратын кез келген x мәні жеткілікті. Кез келген полином p(x) үшін бұл қате 2−p(x) есеге дейін кішірейтилуі мүмкін, бұл үшін полиномдық уақыттан артық емес уақыт немесе логарифмдік кеңістік қолданылмайды, алгоритмді қайталап орындау арқылы.
The probabilistic Turing machines in the definition of RL never accept incorrectly but are allowed to reject incorrectly less than 1/3 of the time; this is called one sided error. The constant 1/3 is arbitrary; any x with 0 < x < 1 would suffice. This error can be made 2−p(x) times smaller for any polynomial p(x) without using more than polynomial time or logarithmic space by running the algorithm repeatedly.
Басқа күрделілік сыныптарымен байланыс
Кейде RL атауы шексіз уақыт ішінде логарифмдік кеңістіктегі ықтималдық автоматтарымен шешілетін мәселелер класы үшін резервтеледі. Дегенмен, бұл класс ықтималдық санауыш арқылы NL-ге тең екенін көрсетуге болады, сондықтан көбінесе NL деп аталады; бұл RL NL класына кіреді екенін көрсетеді. RL, екі жақты қателікке (бұрыс қабылдауға) рұқсат ететін, бірақ ұқсас BPL класына кіреді. RL, детерминистік Тьюринг машиналарымен логарифмдік кеңістікте шешілетін мәселелерді, яғни L класын қамтиды, өйткені оның анықтамасы жай ғана жалпыланған. Ноам Нисан 1992 жылы RL класының SC класына кіретінін көрсетті – бұл детерминистік Тьюринг машинасымен полиномиалдық уақыт және полилогарифмдік кеңістікте шешілетін мәселелер класы; яғни, полилогарифмдік кеңістік берілгенде, детерминистік машина логарифмдік кеңістіктегі ықтималдық алгоритмдерін имитациялай алады. RL класы L класына тең деп есептеледі, яғни полиномиалдық уақыт пен логарифмдік кеңістіктегі есептеуді толығымен кездейсоқтықтан айыруға болады; осыған байланысты маңызды дәлелдерді Рейнгольд және авторлар 2005 жылы ұсынды. Мұның дәлелі күрделілік класстарының шартсыз кездейсоқтықтан айырылу саласындағы күш-жігердің қасиетті мақсаты болып табылады. Омер Рейнгольдтың SL класы L класына тең екенін дәлелдеуі үлкен қадам болды.
Sometimes the name RL is reserved for the class of problems solvable by logarithmic space probabilistic machines in unbounded time. However, this class can be shown to be equal to NL using a probabilistic counter, and so is usually referred to as NL instead; this also shows that RL is contained in NL. RL is contained in BPL, which is similar but allows two sided error (incorrect accepts). RL contains L, the problems solvable by deterministic Turing machines in log space, since its definition is just more general. Noam Nisan showed in 1992 the weak derandomization result that RL is contained in SC, the class of problems solvable in polynomial time and polylogarithmic space on a deterministic Turing machine; in other words, given polylogarithmic space, a deterministic machine can simulate logarithmic space probabilistic algorithms. It is believed that RL is equal to L, that is, that polynomial time logspace computation can be completely derandomized; major evidence for this was presented by Reingold et al. in 2005. A proof of this is the holy grail of the efforts in the field of unconditional derandomization of complexity classes. A major step forward was Omer Reingold's proof that SL is equal to L.