ماشین تورینگ متناوب

توضیحات غیر رسمی

تعریفNPاز حالت وجودی محاسبات استفاده می‌کند: اگر انتخابی منجر به حالت پذیرش شود، در این صورت همهٔ محاسبات پزیرفته می‌شوند. تعریف CO-NP از حالت عمومی محاسبات استفاده می‌کند: اگر همهٔ انتخاب‌ها منجر به حالت پذیرش شوند، در این صورت تمام محاسبات پذیرفته می‌شوند. ماشین تورینگ متقارن (به‌طور دقیق تر، تعریف نحوه پذیرش این ماشین) بین این ۲ حالت در تناوب است.
ماشین تورینگ متقارن ماشین تورینگی غیر قطعی است که حالاتش به ۲ قسمت تقسیم می‌شوند: حالات وجودی و حالات عمومی.
یک حالت وجودی پذیرفته می‌شود اگر انتقالی وجود داشته باشد که منجر به یک حالت پذیرش شود. یک حالت عمومی پذیرفته می‌شود اگر همهٔ انتقال‌ها به حالت پذیرش ختم شوند .(حالت عمومی بدون انتقال، به‌طور پیش فرض پذیرفته و حالت وجودی بدون انتقال به‌طور پیش فرض رد می‌شود). ماشین (به صورت یک واحد) پذیرفته می‌شود اگر حالت اول آن پذیرفته شود.

محدودیت‌های منابع

هنگامی که می‌خوایم پذیرفتنی بودن یا نبودن یک موقعیت از ماشین ATM را طبق تعریف بالا بررسی کنیم، احتیاجی به بررسی تمام حالت‌های دست یافتنی نیست. به‌طور کلی یک موقعیت وجودی در صورتی پذیرفتنی است که هر موقعیتی جانشین آن پذیرفتنی باشد و یک موقعیت عمومی در صورتی پذیرفتنی نیست که هر موقعیتی جانشین آن، پذیرفتنی نباشد.
ماشین تورینگ متقارن زبان‌های صوری (فرمال) را در مرتبهٔ زمانی  پردازش می‌کند اگر به ازای هر رشته به طول ، تعیین پذیرفتنی بودن یا نبودن موقعیت اولی با حد اکثر با  گام امکان‌پذیر باشد
ماشین تورینگ متقارن، زبان را در مرتبهٔ حافظهٔ  پردازش می‌کند اگر تنها بررسی موقعیت‌هایی که تا  خانه از سمت چپ را تغییر نمی‌دهند، کافی باشد.
زبانی که توسط ATM در مرتبهٔ زمانی  (به ازای ) بررسی می‌شود در کلاس  و زبانی که در مرتبهٔ حافظه‌ای  بررسی می‌شود در کلاس  قرار دارد.

مثال

احتمالاً آسان‌ترین مسئلهٔ قابل حل برای ATM، مسئلهٔ quantified Boolean formula problem است. این مسئله تعمیم یافتهٔ مسئلهٔ Boolean satisfiability problem که در آن هر متغیر می‌تواند به یک کمیت عمومی یا وجودی محدود شود.
ATM برای بررسی تمام مقادیر متغیرهای وجودی (از چپ به راست) به صورت وجودی و برای بررسی تمام مقادیر متغیرهای عمومی (از چپ به راست) به صورت عمومی منشعب می‌شود. پس از بررسی یک مقدار برای تمامی متغیرها، اگر نتیجه Boolean formula برابر true باشد ماشین آن را پذیرش و اگر false باشد ماشین آن را نمی‌پذیرد.
بنابر این اگر مقداری جایگزین برای متغیر وجودی، موجود باشد که ادامه مسئله سازگار بماند، یا به ازای تمام مقادیر جایگزین برای متغیر عمومی، ادامه مسئله سازگار باقی بماند، ماشین در شرایط پذیرش قرار می‌گیرد.
این ماشین quantified Boolean formulas را در مرتبهٔ زمانی  و مرتبهٔ حافظه  بررسی می‌کند.
Boolean satisfiability می‌تواند به عنوان حالت خاصی در نظر گرفته شود که در آن تمام متغیرها به صورت وجودی بین شده و فقط از انشعاب به صورت وجودی استفاده برای حل کارایی استفاده می‌شود. در این حالت استفاده از عدم قطعیت مجاز است.

مثال

مسئلهٔ circuit minimization problem را در نظر بگیرید. مدار A که یک تابع بولی F را محاسبه می‌کند، به همراه عدد N به عنوان ورودی داده می‌شوند.
برای خروجی، وجود یا عدم وجود مداری که با K گیت بتواند تابع F را پیاده‌سازی کند، بررسی می‌شود.
ماشین تورینگ متناوبی که یک تناوب دارد و از حالتی وجودی آغاز به کار می‌کند می‌تواند این مسئله را در مرتبهٔ زمانی چند جمله‌ای حل کند.(این کار با آزمایش مدارهای احتمالی با K گیت و مقایسه خروجی آنها با مدار اصلی انجام می‌شود).

پایین آمدن مرتبهٔ کلاس‌ها

یک سلسله مرتبه هنگامی به مرتبهٔ J کاهش پیدا می‌کند که تمام زبان‌های مرتبهٔ K، در مرتبهٔ J موجود باشند. به عنوان نتیجه‌ای از قضیه Immerman–Szelepcsényi theorem، سلسله مراتب حافظه لگاریتهمی، به اولین سطح آن کاهش می‌یابد.

حالت‌های خاص

ماشین تورینگ متناوب با مرتبهٔ زمانی چند جمله‌ای و K تناوب، با شروع از یک حالت وجودی (عمومی) می‌تواند تمام مسائل کلاس () را بررسی کند. از این کلاس‌ها اغلب به صورت() در مسائل یاد می‌شود.
نمونهٔ دیگری از حالات خاص سلسله مراتب زمانی، logarithmic hierarchy است.