Кіріспе

Абстрактілі есептеу моделі

Есептеу күрделілігі теориясында, баламалы Тьюринг машинасы (ATM) – NP және co NP күрделілік сыныптарының анықтамасында қолданылатын қабылдау ережелерін жалпылайтын ережесі бар, детерминистік емес Тьюринг машинасы (NTM). АТМ тұжырымдамасын Чандра мен Стокмейер және Козен 1976 жылы тәуелсіз түрде ұсынды, ал 1981 жылы бірлескен мақала жариялады.

Бейресми сипаттама

NP анықтамасы есептеудің экзистенциалдық режимін пайдаланады: егер кез келген таңдау қабылдау жағдайына жеткізсе, онда бүкіл есептеу қабылданады. Co NP анықтамасы есептеудің әмбебап режимін пайдаланады: егер барлық таңдаулар қабылдау жағдайына жеткізсе ғана, бүкіл есептеу қабылданады. Кезектесетін Тьюринг машинасы (немесе дәлірек айтқанда, мұндай машинаның қабылдау анықтамасы) осы режимдер арасында кезектеседі. Кезектесетін Тьюринг машинасы – күйлері экзистенциалдық күйлер мен әмбебап күйлер деп екі топқа бөлінетін детерминистік емес Тьюринг машинасы. Экзистенциалдық күй, егер бір ауысу қабылдау күйіне жеткізсе, қабылданады; әмбебап күй, егер әрбір ауысу қабылдау күйіне жеткізсе, қабылданады. (Осылайша, ауысуы жоқ әмбебап күй шартсыз қабылданады; ауысуы жоқ экзистенциалдық күй шартсыз қабылдаудан бас тартады). Машинаның өзі бастапқы күйі қабылданатын болса, қабылданады.

Ресурс шектері

Жоғарыда келтірілген анықтама бойынша банкоматтың конфигурациясы қабылдана ма, қабылданбай ма екенін анықтағанда, ағымдағы конфигурациядан қолжетімді барлық конфигурацияларды қарау қажет емес. Атап айтқанда, егер кез келген келесі конфигурация қабылданатын болса, экзистенциалдық конфигурация қабылданатын деп белгіленеді, ал егер кез келген келесі конфигурация қабылданбайтын болса, әмбебап конфигурация қабылданбайтын деп белгіленеді. ATM, егер n ұзындығындағы кез келген кіріс үшін бастапқы конфигурацияны қабылдау немесе қабылдамау үшін тек қадамға дейінгі конфигурацияларды қарау жеткілікті болса, формальды тілді белгілі бір уақытта шешеді. ATM, егер сол жақтанғы жасушадан асып түспейтін таспа жасушаларын өзгертпейтін конфигурацияларды қарау жеткілікті болса, белгілі бір кеңістікте тілді шешеді. Кез келген ATM-мен тұрақты уақыт константасымен шешілген тіл класына жатады, ал кеңістікте шешілген тіл класына жатады.

Мысал

Мүмкін, ауыспалы машиналар шешуге ең қолайлы мәселе – сандық Буль формуласының мәселесі, ол Буль қанағаттандырылатындығы мәселесінің жалпылауы болып табылады, онда әрбір айнымалы экзистенциалдық немесе әмбебап квантормен байланыстырылуы мүмкін. Ауыспалы машина экзистенциалдық квантормен байланысты айнымалының барлық мүмкін мәндерін сынау үшін экзистенциалды түрде тармақталады, ал әмбебап квантормен байланысты айнымалының барлық мүмкін мәндерін сынау үшін әмбебап түрде тармақталады, олар байланысқан тәртіпте – солдан оңға қарай. Барлық сандық айнымалыларға мән бергеннен кейін, машина нәтижесіндегі Буль формуласы шындыққа тең болса, қабылдайды, ал жалғандыққа тең болса, қабылдамайды. Осылайша, экзистенциалдық квантормен байланысты айнымалыда машина, егер айнымалыға қалған мәселені қанағаттандыратын мән қойылса, қабылдайды, ал әмбебап квантормен байланысты айнымалыда машина, егер кез келген мән қойылса және қалған мәселе қанағаттандырылса, қабылдайды. Мұндай машина сандық Буль формулаларын уақыт және кеңістік ішінде шешеді. Буль қанағаттандырылатындығы мәселесін барлық айнымалылар экзистенциалдық квантормен байланыстырылған ерекше жағдай ретінде қарастыруға болады, бұл тек экзистенциалдық тармақтануды қолданатын қарапайым беймәлімдікті тиімді шешуге мүмкіндік береді.

Ерекше жағдайлар

Кезектесіп жұмыс істейтін Тьюринг машинасы полиномиалдық уақытта k ауысумен, экзистенциалдық (сәйкесінше, әмбебап) күйден басталып, (сәйкесінше, ) класындағы барлық мәселелерді шеше алады. Бұл кластар кейде және деп белгіленеді. Толық мәліметтер үшін полиномиялық иерархия мақаласын қараңыз. Уақыт иерархиясының тағы бір ерекше жағдайы – логарифмдік иерархия.