वैकल्पिक ट्यूरिंग मशीन

कम्प्यूटेशनल जटिलता सिद्धांत में, एक वैकल्पिक ट्यूरिंग मशीन (एटीएम) एक गैर-नियतात्मक ट्यूरिंग मशीन (एनटीएम) है जिसमें गणना स्वीकार करने का एक नियम है जो जटिलता वर्गों एनपी (जटिलता) और सह-एनपी की परिभाषा में उपयोग किए जाने वाले नियमों को सामान्य बनाता है। एटीएम की अवधारणा अशोक के. चंद्रा और लैरी स्टॉकमेयर द्वारा प्रस्तुत की गई थी और स्वतंत्र रूप से डेक्सटर कोज़ेन द्वारा 1976 में, 1981 में एक संयुक्त जर्नल प्रकाशन के साथ।

परिभाषाएँ

अनौपचारिक विवरण

एनपी की परिभाषा गणना के अस्तित्वगत मोड का उपयोग करती है: यदि कोई विकल्प स्वीकार्य स्थिति की ओर ले जाता है, तो पूरी गणना स्वीकार हो जाती है। सह-एनपी की परिभाषा गणना के सार्वभौमिक तरीके का उपयोग करती है: केवल तभी जब सभी विकल्प एक स्वीकार्य स्थिति की ओर ले जाते हैं तो पूरी गणना स्वीकार होती है। एक वैकल्पिक ट्यूरिंग मशीन (या अधिक सटीक होने के लिए, ऐसी मशीन के लिए स्वीकृति की परिभाषा) इन मोडों के बीच वैकल्पिक होती है।

'वैकल्पिक ट्यूरिंग मशीन' एक गैर-नियतात्मक ट्यूरिंग मशीन है जिसके राज्यों को दो सेटों में विभाजित किया गया है: 'अस्तित्ववादी राज्य' और 'सार्वभौमिक राज्य'। एक अस्तित्वगत अवस्था स्वीकार करने वाली होती है यदि कोई परिवर्तन स्वीकार करने वाली अवस्था की ओर ले जाता है; एक सार्वभौमिक राज्य स्वीकार कर रहा है यदि प्रत्येक संक्रमण एक स्वीकार्य राज्य की ओर ले जाता है। (इस प्रकार बिना किसी परिवर्तन वाला एक सार्वभौमिक राज्य बिना किसी शर्त के स्वीकार करता है; बिना किसी संक्रमण वाला एक अस्तित्ववादी राज्य बिना किसी शर्त के अस्वीकार करता है)। यदि प्रारंभिक स्थिति स्वीकार कर रही है तो मशीन पूरी तरह से स्वीकार करती है।

औपचारिक परिभाषा

औपचारिक रूप से, एक (एक-टेप) वैकल्पिक ट्यूरिंग मशीन 5-टपल है $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\in Q$ साथ $g(q)=accept$ तब उस कॉन्फ़िगरेशन को स्वीकार करने वाला कहा जाता है, और यदि $g(q)=reject$ कहा जाता है कि कॉन्फ़िगरेशन अस्वीकार हो रहा है. के साथ एक विन्यास $g(q)=\wedge$ ऐसा कहा जाता है कि यदि एक चरण में पहुंच योग्य सभी कॉन्फ़िगरेशन स्वीकार हो रहे हैं, तो इसे स्वीकार किया जा रहा है, और यदि एक चरण में पहुंच योग्य कुछ कॉन्फ़िगरेशन अस्वीकार किया जा रहा है, तो इसे अस्वीकार किया जा रहा है। के साथ एक विन्यास $g(q)=\vee$ इसे तब स्वीकार करना कहा जाता है जब एक चरण में पहुंचने योग्य कुछ कॉन्फ़िगरेशन मौजूद होता है, जिसे स्वीकार करना और अस्वीकार करना होता है जब एक चरण में पहुंच योग्य सभी कॉन्फ़िगरेशन अस्वीकार कर रहे होते हैं (यह अंतिम स्थिति को छोड़कर शास्त्रीय एनटीएम में सभी राज्यों का प्रकार है)। कहा जाता है कि एम एक इनपुट स्ट्रिंग डब्ल्यू को स्वीकार करता है यदि एम का प्रारंभिक विन्यास (एम की स्थिति है $q_{0}$, हेड टेप के बाएं छोर पर है, और टेप में w) स्वीकार करना है, और यदि प्रारंभिक कॉन्फ़िगरेशन अस्वीकार कर रहा है तो अस्वीकार करना है।

ध्यान दें कि किसी कॉन्फ़िगरेशन के लिए स्वीकार करना और अस्वीकार करना दोनों असंभव है, हालांकि, गैर-समाप्ति गणना की संभावना के कारण, कुछ कॉन्फ़िगरेशन न तो स्वीकार कर सकते हैं और न ही अस्वीकार कर सकते हैं।

संसाधन सीमा

उपरोक्त परिभाषा का उपयोग करते हुए यह तय करते समय कि एटीएम का कॉन्फ़िगरेशन स्वीकार या अस्वीकार कर रहा है, वर्तमान कॉन्फ़िगरेशन से पहुंच योग्य सभी कॉन्फ़िगरेशन की जांच करना हमेशा आवश्यक नहीं होता है। विशेष रूप से, एक अस्तित्वगत कॉन्फ़िगरेशन को स्वीकार करने के रूप में लेबल किया जा सकता है यदि कोई उत्तराधिकारी कॉन्फ़िगरेशन स्वीकार करने योग्य पाया जाता है, और एक सार्वभौमिक कॉन्फ़िगरेशन को अस्वीकार करने के रूप में लेबल किया जा सकता है यदि कोई उत्तराधिकारी कॉन्फ़िगरेशन अस्वीकार करता हुआ पाया जाता है।

एटीएम समय रहते औपचारिक भाषा तय कर लेता है $t(n)$ यदि, लंबाई के किसी भी इनपुट पर n, तक ही कॉन्फ़िगरेशन की जांच कर रहा है $t(n)$ प्रारंभिक कॉन्फ़िगरेशन को स्वीकार या अस्वीकार के रूप में लेबल करने के लिए चरण पर्याप्त हैं। एक एटीएम अंतरिक्ष में एक भाषा तय करता है $s(n)$ यदि उन कॉन्फ़िगरेशनों की जांच की जा रही है जो टेप कोशिकाओं को इससे परे संशोधित नहीं करते हैं $s(n)$ बायीं ओर से सेल पर्याप्त है.

एक ऐसी भाषा जो समय के साथ कुछ एटीएम द्वारा तय की जाती है $c\cdot t(n)$ कुछ स्थिरांक के लिए $c>0$ कहा जाता है कि वह कक्षा में है ${\mathsf {ATIME}}(t(n))$, और अंतरिक्ष में एक भाषा तय की गई $c\cdot s(n)$ कहा जाता है कि वह कक्षा में है ${\mathsf {ASPACE}}(s(n))$.

उदाहरण

शायद वैकल्पिक मशीनों को हल करने के लिए सबसे स्वाभाविक समस्या मात्रात्मक बूलियन सूत्र समस्या है, जो बूलियन संतुष्टि समस्या का एक सामान्यीकरण है जिसमें प्रत्येक चर को अस्तित्वगत या सार्वभौमिक मात्रात्मक द्वारा बाध्य किया जा सकता है। वैकल्पिक मशीन शाखाएँ अस्तित्वगत रूप से परिमाणित चर के सभी संभावित मूल्यों को आज़माने के लिए और सार्वभौमिक रूप से सार्वभौमिक रूप से परिमाणित चर के सभी संभावित मूल्यों को बाएँ से दाएँ क्रम में आज़माने के लिए, जिसमें वे बंधे हैं। सभी परिमाणित चरों के लिए एक मान तय करने के बाद, यदि परिणामी बूलियन सूत्र सत्य का मूल्यांकन करता है तो मशीन स्वीकार कर लेती है, और यदि गलत का मूल्यांकन करती है तो अस्वीकार कर देती है। इस प्रकार अस्तित्वगत रूप से परिमाणित चर पर मशीन स्वीकार कर रही है कि क्या चर के लिए एक मान प्रतिस्थापित किया जा सकता है जो शेष समस्या को संतोषजनक बनाता है, और एक सार्वभौमिक रूप से परिमाणित चर पर मशीन स्वीकार कर रही है कि क्या कोई मान प्रतिस्थापित किया जा सकता है और शेष समस्या संतोषजनक है।

ऐसी मशीन समय पर परिमाणित बूलियन सूत्र तय करती है $n^{2}$ और स्थान $n$.

बूलियन संतुष्टि समस्या को विशेष मामले के रूप में देखा जा सकता है जहां सभी चर अस्तित्वगत रूप से परिमाणित होते हैं, जो सामान्य गैर-नियतिवाद को अनुमति देता है, जो इसे कुशलतापूर्वक हल करने के लिए केवल अस्तित्वगत शाखा का उपयोग करता है।

जटिलता वर्ग और नियतात्मक ट्यूरिंग मशीनों से तुलना

निम्नलिखित जटिलता वर्ग एटीएम के लिए परिभाषित करने के लिए उपयोगी हैं:

• ${\mathsf {AP}}=\bigcup _{k>0}{\mathsf {ATIME}}(n^{k})$ क्या भाषाएँ बहुपद समय में निर्णय लेने योग्य हैं?
• ${\mathsf {APSPACE}}=\bigcup _{k>0}{\mathsf {ASPACE}}(n^{k})$ बहुपद स्थान में निर्णय लेने योग्य भाषाएँ हैं
• ${\mathsf {AEXPTIME}}=\bigcup _{k>0}{\mathsf {ATIME}}(2^{n^{k}})$ क्या भाषाएँ घातीय समय में निर्णय लेने योग्य हैं

ये एक नियतात्मक ट्यूरिंग मशीन के बजाय एटीएम द्वारा उपयोग किए जाने वाले संसाधनों पर विचार करते हुए, पी (जटिलता), पीएसपीएसीई और एक्सटाइम की परिभाषाओं के समान हैं। चंद्रा, कोज़ेन, और स्टॉकमेयरप्रमेयों को सिद्ध किया

• एलॉगस्पेस = पी
• एपी = पीस्पेस
• एपस्पेस = एक्सटाइम
• एक्सपीटाइम = एक्सस्पेस
• ${\mathsf {ASPACE}}(f(n))=\bigcup _{c>0}{\mathsf {DTIME}}(2^{cf(n)})={\mathsf {DTIME}}(2^{O(f(n))})$
• ${\mathsf {ATIME}}(g(n))\subseteq {\mathsf {DSPACE}}(g(n))$
• ${\mathsf {NSPACE}}(g(n))\subseteq \bigcup _{c>0}{\mathsf {ATIME}}(c\times g(n)^{2}),$

कब $f(n)\geq \log(n)$ और $g(n)\geq \log(n)$.

इन संबंधों का अधिक सामान्य रूप समानांतर गणना थीसिस द्वारा व्यक्त किया गया है।

परिबद्ध प्रत्यावर्तन

परिभाषा

k विकल्पों के साथ एक वैकल्पिक ट्यूरिंग मशीन एक वैकल्पिक ट्यूरिंग मशीन है जो अस्तित्वगत से सार्वभौमिक स्थिति में या इसके विपरीत k-1 बार से अधिक स्विच नहीं करती है। (यह एक वैकल्पिक ट्यूरिंग मशीन है जिसके राज्य k सेट में विभाजित हैं। सम-संख्या वाले सेट में राज्य सार्वभौमिक हैं और विषम संख्या वाले सेट में राज्य अस्तित्वगत हैं (या इसके विपरीत)। मशीन में सेट i और सेट j <'i में एक राज्य के बीच कोई संक्रमण नहीं है।)

${\mathsf {ATIME}}(C,j)=\Sigma _{j}{\mathsf {TIME}}(C)$ समय के अनुसार निर्णय लेने योग्य भाषाओं का वर्ग है $f\in C$ एक मशीन द्वारा जो अस्तित्वगत अवस्था में शुरू होती है और अधिक से अधिक बदलती रहती है $j-1$ बार. इसे कहा जाता है jवें स्तर का ${\mathsf {TIME}}(C)$ पदानुक्रम।

${\mathsf {coATIME}}(C,j)=\Pi _{j}{\mathsf {TIME}}(C)$ उसी तरह से परिभाषित किया गया है, लेकिन एक सार्वभौमिक स्थिति में शुरू होता है; इसमें भाषाओं के पूरक शामिल हैं ${\mathsf {ATIME}}(f,j)$.

${\mathsf {ASPACE}}(C,j)=\Sigma _{j}{\mathsf {SPACE}}(C)$ अंतरिक्षबद्ध संगणना के लिए इसी प्रकार परिभाषित किया गया है।

उदाहरण

सर्किट न्यूनीकरण समस्या पर विचार करें: एक सर्किट ए को एक बूलियन फ़ंक्शन एफ और एक संख्या एन की गणना करते हुए, यह निर्धारित करें कि क्या अधिकतम एन गेट्स वाला एक सर्किट है जो समान फ़ंक्शन एफ की गणना करता है। एक प्रत्यावर्ती ट्यूरिंग मशीन, एक प्रत्यावर्तन के साथ, एक अस्तित्वगत स्थिति में शुरू करके, इस समस्या को बहुपद समय में हल कर सकती है (अधिकतम n द्वारों के साथ एक सर्किट बी का अनुमान लगाकर, फिर एक सार्वभौमिक स्थिति पर स्विच करके, एक इनपुट का अनुमान लगाकर, और यह जांच कर कि उस इनपुट पर बी का आउटपुट उस इनपुट पर ए के आउटपुट से मेल खाता है)।

ढहती हुई कक्षाएं

ऐसा कहा जाता है कि पदानुक्रम स्तर तक ढह जाता है j यदि प्रत्येक भाषा स्तर में है $k\geq j$ पदानुक्रम का स्तर अपने स्तर पर है j.

इमरमैन-स्ज़ेलेपेसेनी प्रमेय के परिणाम के रूप में, लॉगरिदमिक अंतरिक्ष पदानुक्रम अपने पहले स्तर तक ढह जाता है। एक परिणाम के रूप में ${\mathsf {SPACE}}(f)$ जब पदानुक्रम अपने पहले स्तर तक ढह जाता है $f=\Omega (\log )$ स्थान निर्माण योग्य है.

विशेष मामले

K विकल्पों के साथ बहुपद समय में एक वैकल्पिक ट्यूरिंग मशीन, अस्तित्वगत (क्रमशः, सार्वभौमिक) स्थिति में शुरू होकर कक्षा की सभी समस्याओं का समाधान कर सकती है $\Sigma _{k}^{p}$ (क्रमश, $\Pi _{k}^{p}$). इन वर्गों को कभी-कभी निरूपित किया जाता है $\Sigma _{k}{\rm {P}}$ और $\Pi _{k}{\rm {P}}$, क्रमश। विवरण के लिए बहुपद पदानुक्रम लेख देखें।

समय पदानुक्रम का एक और विशेष मामला एलएच (जटिलता) है।

अग्रिम पठन

• Michael Sipser (2006). Introduction to the Theory of Computation (2nd ed.). PWS Publishing. ISBN 978-0-534-95097-2. Section 10.3: Alternation, pp. 380–386.
• Christos Papadimitriou (1993). Computational Complexity (1st ed.). Addison Wesley. ISBN 978-0-201-53082-7. Section 16.2: Alternation, pp. 399–401.
• Bakhadyr Khoussainov; Anil Nerode (2012). Automata Theory and its Applications. Springer Science & Business Media. ISBN 978-1-4612-0171-7.