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

در نظریه پیچیدگی محاسباتی، یک ماشین تورینگ متناوب (به انگلیسی: Alternating Turing machine) (مخفف انگلیسی: ATM)، ماشین تورینگی غیر قطعی است و شامل قانونی برای پذیرش محاسباتی است که قوانین استفاده شده در تعریف کلاس‌های پیچیدگی NP و co-NP را کلیت می‌بخشد. مفهوم ATM توسط Chandra و Stockmeyer و مستقلاً توسط Kozen در سال ۱۹۷۶، و سپس به صورت مشترک، باانتشار در یک مجله در سال ۱۹۸۱ مطرح شد.

تعاریف

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

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

تعریف علمی

ماشین تورینگ متقارن یک ۵ تایی به صورت$M=(Q,\Gamma ,\delta ,q_{0},g)$است که:

• $Q$مجموعه متناهی از حالت است.
• $\Gamma$ مجموعه متناهی الفبای نوار است.
• $\delta :Q\times \Gamma \rightarrow {\mathcal {P}}(Q\times \Gamma \times \{L,R\})$ تابع انتقال نام دارد (L کلاهک را به سمت چپ و R کلاهک را به سمت راست می‌برد)
• $q_{0}\in Q$ حالت اولیه است.
• $g:Q\rightarrow \{\wedge ,\vee ,accept,reject\}$ نوع هر حالت را مشخص می‌کند.

اگرM در وضعیت Q با $g(q)=accept$ باشد، در این صورت این موقعیت، موقعیتی پذیرفتنی است و اگر $g(q)=reject$، موقعیتی پذیرفتنی نیست.

موقعیتی با $g(q)=\wedge$ پذیرفتنی است اگر همهٔ موقعیت‌هایی که با یک گام می‌توان به آن‌ها دست یافت پذیرفتنی باشند و غیر پذیرفتنی است اگر بعضی از موقعیت‌هایی که با یک گام قابل دسترسی هستند غیر پذیرفتنی باشند.

موقعیتی با $g(q)=\vee$ موقعیتی پذیرفتنی است اگر موقعیتی پذیرفتنی وجود داشته باشد که با یک گام بتوان به آن دست یافت و غیر پذیرفتنی است اگر تمام موقعیت‌هایی که بتوان طی یک گام به آنها دست یافت، غیر پذیرفتنی باشند. ماشین M رشتهٔ W را در صورتی می‌پذیرد که موقعیت اولیه آن پذیرفتنی باشد و در صورتی آن را رد می‌کند که موقعیت اولیه آن پذیرفتنی نباشد.

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

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

ماشین تورینگ متقارن زبان‌های صوری (فرمال) را در مرتبهٔ زمانی $t(n)$ پردازش می‌کند اگر به ازای هر رشته به طول $n$، تعیین پذیرفتنی بودن یا نبودن موقعیت اولی با حد اکثر با $t(n)$ گام امکان‌پذیر باشد

ماشین تورینگ متقارن، زبان را در مرتبهٔ حافظهٔ $s(n)$ پردازش می‌کند اگر تنها بررسی موقعیت‌هایی که تا $s(n)$ خانه از سمت چپ را تغییر نمی‌دهند، کافی باشد.

زبانی که توسط ATM در مرتبهٔ زمانی $c\cdot t(n)$ (به ازای $c>0$) بررسی می‌شود در کلاس ${\rm {ATIME}}(t(n))$ و زبانی که در مرتبهٔ حافظه‌ای $c\cdot s(n)$ بررسی می‌شود در کلاس ${\rm {ASPACE}}(s(n))$ قرار دارد.

مثال

احتمالاً آسان‌ترین مسئلهٔ قابل حل برای ATM، مسئلهٔ quantified Boolean formula problem است. این مسئله تعمیم یافتهٔ مسئلهٔ Boolean satisfiability problem که در آن هر متغیر می‌تواند به یک کمیت عمومی یا وجودی محدود شود.

ATM برای بررسی تمام مقادیر متغیرهای وجودی (از چپ به راست) به صورت وجودی و برای بررسی تمام مقادیر متغیرهای عمومی (از چپ به راست) به صورت عمومی منشعب می‌شود. پس از بررسی یک مقدار برای تمامی متغیرها، اگر نتیجه Boolean formula برابر true باشد ماشین آن را پذیرش و اگر false باشد ماشین آن را نمی‌پذیرد.

بنابر این اگر مقداری جایگزین برای متغیر وجودی، موجود باشد که ادامه مسئله سازگار بماند، یا به ازای تمام مقادیر جایگزین برای متغیر عمومی، ادامه مسئله سازگار باقی بماند، ماشین در شرایط پذیرش قرار می‌گیرد.

این ماشین quantified Boolean formulas را در مرتبهٔ زمانی $n^{2}$ و مرتبهٔ حافظه $n$ بررسی می‌کند.

Boolean satisfiability می‌تواند به عنوان حالت خاصی در نظر گرفته شود که در آن تمام متغیرها به صورت وجودی بین شده و فقط از انشعاب به صورت وجودی استفاده برای حل کارایی استفاده می‌شود. در این حالت استفاده از عدم قطعیت مجاز است.

کلاس‌های پیچیدگی و مقایسه با ماشین تورینگ قطعی

کلاس‌های پیچیدگی زیر برای تعریف ماشین تورینگ متناوب مورد استفاده قرار می‌گیرند:

• ${\rm {AP}}=\bigcup _{k>0}{\rm {ATIME}}(n^{k})$ زبان‌هایی هستند که در مرتبهٔ زمانی چند جمله‌ای بررسی می‌شوند.
• ${\rm {APSPACE}}=\bigcup _{k>0}{\rm {ASPACE}}(n^{k})$ زبان‌هایی هستند که در مرتبهٔ حافظه‌ای چند جمله‌ای بررسی می‌شوند.
• ${\rm {AEXPTIME}}=\bigcup _{k>0}{\rm {ATIME}}(k^{n})$ زبان‌هایی هستند که در مرتبهٔ زمانی نمائی بررسی می‌شوند.

این کلاس‌ها، با در نظر گرفتن منابعی که یک ATM به جای ماشین تورینگ قطعی استفاده می‌کند، شبیه به تعریف‌های P و PSPACE و EXPTIME هستند.

Chandra, Kozen, و Stockmeyer قضایای زیر را در شرایطی که $f(n)\geq \log(n)$ و $g(n)\geq \log(n)$ ثابت کرده‌اند.

• AP = PSPACE
• APSPACE = EXPTIME
• AEXPTIME = EXPSPACE
• $\mathrm {ASPACE} (f(n))=\bigcup _{c>0}{\rm {DTIME}}(2^{cf(n)})={\rm {DTIME}}(2^{O(f(n))})$
• $\mathrm {ATIME} (g(n))\subseteq {\rm {DSPACE}}(g(n))$
• $\mathrm {NSPACE} (g(n))\subseteq \bigcup _{c>0}{\rm {ATIME}}(c\times g(n)^{2}),$

شکل کلی تر این روابط توسط تز پردازش موازی، نشان داده می‌شود.

تناوب محدود

تعریف

ماشین تورینگ متناوب با K تناوب، ماشین تورینگی متناوب است که حد اکثر K-1 دفعه می‌تواند بین حالت عمومی و حالت وجودی جابجا شود .(در واقع ماشین تورینگی است که حالت‌هایش به K مجموعه تقسیم شده‌اند. حالت‌های با شمارهٔ فرد حالت‌های عمومی و حالت‌های با شماره زوج حالت‌های وجودی در نظر گرفته می‌شوند (عکس آن هم درست است). ماشین هیچ انتقالی از حالت i به j، که j<i، ندارد)

• ${\rm {ATIME}}(C,j)=\Sigma _{j}{\rm {TIME}}(C)$ کلاس توابعی است که که در زمان $f\in C$، از یک حالت وجودی شروع می‌شوند و حد اکثر j-1 بر تناوب می‌کنند و به آن j-امین سطح از سلسله مراتب ${\rm {TIME}}(C)$ هم گفته می‌شود
• ${\rm {coATIME}}(C,j)=\Pi _{j}{\rm {TIME}}(C)$ کلاسی مشابه با کلاس قبلی است با این تفاوت که از یک حالت عمومی شروع می‌شود و متمم زبان ${\rm {ATIME}}(f,j)$ است.

${\rm {ASPACE}}(C,j)=\Sigma _{\rm {SPACE}}(C)$ به صورت مشابه برای محاسبات با حافظهٔ محدود تعریف می‌شود.

مثال

مسئلهٔ circuit minimization problem را در نظر بگیرید. مدار A که یک تابع بولی F را محاسبه می‌کند، به همراه عدد N به عنوان ورودی داده می‌شوند.

برای خروجی، وجود یا عدم وجود مداری که با K گیت بتواند تابع F را پیاده‌سازی کند، بررسی می‌شود.

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

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

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

حالت‌های خاص

ماشین تورینگ متناوب با مرتبهٔ زمانی چند جمله‌ای و K تناوب، با شروع از یک حالت وجودی (عمومی) می‌تواند تمام مسائل کلاس $\Sigma _{k}^{p}$($\Pi _{k}^{p}$) را بررسی کند. از این کلاس‌ها اغلب به صورت$\Sigma _{k}{\rm {P}}$($\Pi _{k}{\rm {P}}$) در مسائل یاد می‌شود.

نمونهٔ دیگری از حالات خاص سلسله مراتب زمانی، logarithmic hierarchy است.

منابع

• Michael Sipser (1997). Introduction to the Theory of Computation. PWS Publishing. ISBN 0-534-94728-X. Section 10.3: Alternation, pp.  ۳۴۸–۳۵۴.
• Michael Sipser (2006). Introduction to the Theory of Computation, 2nd ed. PWS Publishing. ISBN 0-534-95097-3. Section 10.3: Alternation, pp.  ۳۸۰–۳۸۶.
• Christos Papadimitriou (1993). Computational Complexity (1st edition ed.). Addison Wesley. ISBN 0-201-53082-1. {{cite book}}: |edition= has extra text (help) Section 16.2: Alternation, pp.  ۳۹۹–۴۰۱.