आरई (जटिलता): Difference between revisions
From Vigyanwiki
(Created page with "कम्प्यूटेबिलिटी सिद्धांत और कम्प्यूटेशनल जटिलता सिद्धांत में,...") |
No edit summary |
||
| Line 1: | Line 1: | ||
कम्प्यूटेबिलिटी सिद्धांत और [[कम्प्यूटेशनल जटिलता सिद्धांत]] में, आरई ([[पुनरावर्ती गणना योग्य सेट]]) [[निर्णय समस्या]]ओं की [[जटिलता वर्ग]] है | कम्प्यूटेबिलिटी सिद्धांत और [[कम्प्यूटेशनल जटिलता सिद्धांत]] में, आरई ([[पुनरावर्ती गणना योग्य सेट]]) [[निर्णय समस्या]]ओं की [[जटिलता वर्ग]] है जिसके लिए एक 'हां' उत्तर को [[ट्यूरिंग मशीन]] द्वारा सीमित समय में सत्यापित किया जा सकता है।<ref>{{CZoo|Class RE|R#re}}</ref> अनौपचारिक रूप से इसका अर्थ है कि यदि किसी समस्या के उदाहरण का उत्तर 'हां' है, तो कुछ ऐसी प्रक्रिया है जो इसे निर्धारित करने के लिए परिमित समय लेती है और यह प्रक्रिया कभी भी गलत विधि से 'हां' की सूचना नहीं देती है जब सही उत्तर 'नहीं' होता है। चूँकि जब सही उत्तर 'नहीं' है तो प्रक्रिया को रोकने की आवश्यकता नहीं है यह कुछ 'नहीं' स्थिति के लिए [[अनंत लूप]] में जा सकता है। इस तरह की प्रक्रिया को कभी-कभी अर्ध-एल्गोरिदम कहा जाता है, इसे एक [[कलन विधि]] से अलग करने के लिए एक निर्णय समस्या के पूर्ण समाधान के रूप में परिभाषित किया जाता है।<ref>{{cite book |first=Robert R. |last=Korfhage |year=1966 |title=तर्क और एल्गोरिदम, कंप्यूटर और सूचना विज्ञान के अनुप्रयोगों के साथ|url=https://archive.org/details/logicalgorithmsw0000korf |url-access=registration |publisher=Wiley |page=[https://archive.org/details/logicalgorithmsw0000korf/page/89 89] |quote=A method of solution will be called a ''semi-algorithm'' for [a problem] ''P'' on [a device] ''M'' if the solution to ''P'' (if one exists) appears after the performance of finitely many steps. A semi-algorithm will be called an ''[[algorithm]]'' if, in addition, whenever the problem has no solution the method enables the device to determine this after a finite number of steps and halts.}}</ref> | ||
इसी तरह | |||
इसी तरह सह-आरई उन सभी भाषाओं का समूह है जो आरई में एक भाषा की पूरक हैं। एक अर्थ में, सह-आरई में ऐसी भाषाएं होती हैं जिनकी सदस्यता को सीमित समय में अस्वीकृत किया जा सकता है किंतु सदस्यता सिद्ध करने में सदैव के लिए लग सकता है। | |||
== समतुल्य परिभाषा == | == समतुल्य परिभाषा == | ||
समतुल्य रूप से, आरई निर्णय समस्याओं का वर्ग है जिसके लिए एक ट्यूरिंग मशीन सभी 'हां' उदाहरणों को एक-एक करके सूचीबद्ध कर सकती है (यह 'गणना योग्य' का अर्थ है)। | समतुल्य रूप से, आरई निर्णय समस्याओं का वर्ग है जिसके लिए एक ट्यूरिंग मशीन सभी 'हां' उदाहरणों को एक-एक करके सूचीबद्ध कर सकती है (यह 'गणना योग्य' का अर्थ है)। | ||
यह दिखाने के लिए समतुल्य है, ध्यान दें कि यदि कोई मशीन | आरई का प्रत्येक सदस्य एक पुनरावर्ती गणना योग्य समुच्चय है और इसलिए एक [[डायोफैंटाइन सेट|डायोफैंटाइन]] समुच्चय है। | ||
यह दिखाने के लिए कि यह समतुल्य है, ध्यान दें कि यदि कोई मशीन <math>E</math> है जो सभी स्वीकृत इनपुटों की गणना करती है, तो दूसरी मशीन जो स्ट्रिंग में लेती है, <math>E</math> चला सकती है और यदि स्ट्रिंग की गणना की जाती है तो स्वीकार कर सकती है। इसके विपरीत, यदि कोई मशीन <math>M</math> किसी भाषा में इनपुट होने पर स्वीकार करती है, तो दूसरी मशीन प्रत्येक इनपुट पर <math>M</math> के सिमुलेशन को इंटरलीविंग करके और स्वीकार किए जाने वाले स्ट्रिंग्स को आउटपुट करके भाषा में सभी स्ट्रिंग्स की गणना कर सकती है (निष्पादन का एक क्रम है जो अंततः प्राप्त होगा प्रत्येक निष्पादन चरण क्योंकि इनपुट और चरणों के कई क्रमित जोड़े हैं)। | |||
== अन्य वर्गों से संबंध == | == अन्य वर्गों से संबंध == | ||
[[पुनरावर्ती भाषा]]ओं का | [[पुनरावर्ती भाषा]]ओं का समुच्चय ([[आर (जटिलता)]]) आरई और सह-आरई दोनों का एक सबसेट है।<ref>{{CZoo|Class co-RE|C#core}}</ref> वास्तव में यह उन दो वर्गों का प्रतिच्छेदन है क्योंकि हम किसी भी समस्या का निर्णय ले सकते हैं जिसके लिए एक पहचानकर्ता और एक सह-पहचानकर्ता उपस्थित है जब तक कि कोई परिणाम प्राप्त न हो जाए। इसलिए: | ||
:<math>\mbox{R} = \mbox{RE}\cap\mbox{co-RE}</math>. | :<math>\mbox{R} = \mbox{RE}\cap\mbox{co-RE}</math>. | ||
इसके विपरीत | इसके विपरीत भाषाओं का समूह जो न तो आरई है और न ही सह-आरई एनआरएनसी के रूप में जाना जाता है। ये भाषाओं का समूह हैं जिसके लिए न तो सदस्यता और न ही गैर-सदस्यता को सीमित समय में सिद्ध किया जा सकता है और इसमें अन्य सभी भाषाएँ सम्मिलित हैं जो आरई या सह-आरई में नहीं हैं। वह है: | ||
:<math>\mbox{NRNC} = \mbox{ALL} - (\mbox{RE}\cup\mbox{co-RE})</math>. | :<math>\mbox{NRNC} = \mbox{ALL} - (\mbox{RE}\cup\mbox{co-RE})</math>. | ||
न केवल ये समस्याएं अनिर्णीत हैं | न केवल ये समस्याएं अनिर्णीत हैं किंतु न तो वे और न ही उनके पूरक पुनरावर्ती गणना योग्य हैं। | ||
2020 के जनवरी में | 2020 के जनवरी में एक प्रीप्रिंट ने एक प्रमाण की घोषणा की कि आरई वर्ग एमआईपी * के समान था (वह वर्ग जहां एक मौलिक सत्यापनकर्ता कई सर्व-शक्तिशाली क्वांटम प्रोवर्स के साथ बातचीत करता है जो क्वांटम उलझाव साझा करते हैं);<ref>{{cite arXiv |last1=Ji |first1=Zhengfeng |last2=Natarajan |first2=Anand |last3=Vidick |first3=Thomas |last4=Wright |first4=John |last5=Yuen |first5=Henry |title=MIP*=RE |year=2020 |class=quant-ph |eprint=2001.04383 }}</ref> एक संशोधित किंतु अभी तक पूरी तरह से समीक्षा नहीं की गई, प्रमाण नवंबर 2021 में एसीएम के संचार में प्रकाशित किया गया था। प्रमाण का अर्थ है कि कोन्स एम्बेडिंग समस्या और त्सिरेलसन की समस्या असत्य है।<ref>{{cite journal |last1=Ji |first1=Zhengfeng |last2=Natarajan |first2=Anand |last3=Vidick |first3=Thomas |last4=Wright |first4=John |last5=Yuen |first5=Henry |title=MIP* = RE |journal=Communications of the ACM |date=November 2021 |volume=64 |issue=11 |pages=131–138 |doi=10.1145/3485628|s2cid=210165045 }}</ref> | ||
== आरई-पूर्ण == | == आरई-पूर्ण == | ||
आरई-पूर्ण निर्णय समस्याओं का समूह है जो आरई के लिए पूर्ण हैं। एक | आरई-पूर्ण निर्णय समस्याओं का समूह है जो आरई के लिए पूर्ण हैं। एक माध्यम में ये सबसे कठिन पुनरावर्ती गणना योग्य समस्याएं हैं। सामान्यतः उपयोग की जाने वाली कमी पर कोई प्रतिबंध नहीं लगाया जाता है अतिरिक्त इसके कि वे कई-एक कमी होनी चाहिए। | ||
आरई-पूर्ण समस्याओं के उदाहरण: | आरई-पूर्ण समस्याओं के उदाहरण: | ||
# हॉल्टिंग की समस्या: क्या एक सीमित इनपुट दिया गया प्रोग्राम चलना समाप्त करता है या | # हॉल्टिंग की समस्या: क्या एक सीमित इनपुट दिया गया प्रोग्राम चलना समाप्त करता है या सदैव के लिए चलेगा। | ||
# राइस के प्रमेय द्वारा | # राइस के प्रमेय द्वारा [[संगणनीय समारोह|संगणनीय कार्य]] के समुच्चय के किसी भी गैर-तुच्छ उपसमुच्चय में सदस्यता तय करना आरई-कठिन है। जब भी समुच्चय पुनरावर्ती रूप से गणनीय होगा, यह पूरा हो जाएगा। | ||
#{{harvs|first=John|last=Myhill|authorlink=John Myhill|year=1955|txt}}<ref>{{citation | #{{harvs|first=John|last=Myhill|authorlink=John Myhill|year=1955|txt}}<ref>{{citation | ||
| last = Myhill | first = John | authorlink = John Myhill | | last = Myhill | first = John | authorlink = John Myhill | ||
| Line 35: | Line 37: | ||
| title = Creative sets | | title = Creative sets | ||
| volume = 1 | | volume = 1 | ||
| issue = 2 | year = 1955}}.</ref> | | issue = 2 | year = 1955}}.</ref> सिद्ध कर दिया कि सभी [[रचनात्मक सेट|रचनात्मक]] समुच्चय आरई-पूर्ण हैं। | ||
# [[समूह (गणित)]] या अर्धसमूहों के लिए समान [[शब्द समस्या (गणित)]]। (वास्तव में | # [[समूह (गणित)]] या अर्धसमूहों के लिए समान [[शब्द समस्या (गणित)]]। (वास्तव में [[समूहों के लिए शब्द समस्या]] आरई-पूर्ण है।) | ||
# एक सामान्य [[अप्रतिबंधित व्याकरण]] [[औपचारिक व्याकरण]] में सदस्यता तय करना। (फिर से | # एक सामान्य [[अप्रतिबंधित व्याकरण]] [[औपचारिक व्याकरण]] में सदस्यता तय करना। (फिर से कुछ व्यक्तिगत व्याकरणों में आरई-पूर्ण सदस्यता समस्याएँ हैं।) | ||
# प्रथम क्रम तर्क के लिए [[वैधता (तर्क)]] समस्या। | # प्रथम क्रम तर्क के लिए [[वैधता (तर्क)]] समस्या। | ||
# पोस्ट पत्राचार समस्या: तार के जोड़े की एक सूची को देखते हुए | # पोस्ट पत्राचार समस्या: तार के जोड़े की एक सूची को देखते हुए निर्धारित करें कि क्या इन जोड़ियों में से कोई चयन है (दोहराव की अनुमति) जैसे कि पहले आइटम (जोड़े के) का संयोजन दूसरे आइटम के संयोजन के समान है। | ||
# यह निर्धारित करना कि [[डायोफैंटाइन समीकरण]] का कोई पूर्णांक समाधान है या नहीं। | # यह निर्धारित करना कि [[डायोफैंटाइन समीकरण]] का कोई पूर्णांक समाधान है या नहीं। | ||
== सह-आरई-पूर्ण == | == सह-आरई-पूर्ण == | ||
सह-आरई-पूर्ण निर्णय समस्याओं का समूह है जो सह-आरई के लिए पूर्ण हैं। एक | सह-आरई-पूर्ण निर्णय समस्याओं का समूह है जो सह-आरई के लिए पूर्ण हैं। एक माध्यम में ये सबसे कठिन पुनरावर्ती गणना योग्य समस्याओं के पूरक हैं। | ||
सह-आरई-पूर्ण समस्याओं के उदाहरण: | सह-आरई-पूर्ण समस्याओं के उदाहरण: | ||
| Line 54: | Line 56: | ||
* [[बहुरूपी पुनरावर्तन]] | * [[बहुरूपी पुनरावर्तन]] | ||
* [[रिस्क एल्गोरिथम]] | * [[रिस्क एल्गोरिथम]] | ||
* निर्णायकता_(तर्क) | * निर्णायकता_(तर्क) या अर्ध-अम्लीयता | ||
==संदर्भ== | ==संदर्भ== | ||
Revision as of 11:38, 2 June 2023
कम्प्यूटेबिलिटी सिद्धांत और कम्प्यूटेशनल जटिलता सिद्धांत में, आरई (पुनरावर्ती गणना योग्य सेट) निर्णय समस्याओं की जटिलता वर्ग है जिसके लिए एक 'हां' उत्तर को ट्यूरिंग मशीन द्वारा सीमित समय में सत्यापित किया जा सकता है।[1] अनौपचारिक रूप से इसका अर्थ है कि यदि किसी समस्या के उदाहरण का उत्तर 'हां' है, तो कुछ ऐसी प्रक्रिया है जो इसे निर्धारित करने के लिए परिमित समय लेती है और यह प्रक्रिया कभी भी गलत विधि से 'हां' की सूचना नहीं देती है जब सही उत्तर 'नहीं' होता है। चूँकि जब सही उत्तर 'नहीं' है तो प्रक्रिया को रोकने की आवश्यकता नहीं है यह कुछ 'नहीं' स्थिति के लिए अनंत लूप में जा सकता है। इस तरह की प्रक्रिया को कभी-कभी अर्ध-एल्गोरिदम कहा जाता है, इसे एक कलन विधि से अलग करने के लिए एक निर्णय समस्या के पूर्ण समाधान के रूप में परिभाषित किया जाता है।[2]
इसी तरह सह-आरई उन सभी भाषाओं का समूह है जो आरई में एक भाषा की पूरक हैं। एक अर्थ में, सह-आरई में ऐसी भाषाएं होती हैं जिनकी सदस्यता को सीमित समय में अस्वीकृत किया जा सकता है किंतु सदस्यता सिद्ध करने में सदैव के लिए लग सकता है।
समतुल्य परिभाषा
समतुल्य रूप से, आरई निर्णय समस्याओं का वर्ग है जिसके लिए एक ट्यूरिंग मशीन सभी 'हां' उदाहरणों को एक-एक करके सूचीबद्ध कर सकती है (यह 'गणना योग्य' का अर्थ है)।
आरई का प्रत्येक सदस्य एक पुनरावर्ती गणना योग्य समुच्चय है और इसलिए एक डायोफैंटाइन समुच्चय है।
यह दिखाने के लिए कि यह समतुल्य है, ध्यान दें कि यदि कोई मशीन है जो सभी स्वीकृत इनपुटों की गणना करती है, तो दूसरी मशीन जो स्ट्रिंग में लेती है, चला सकती है और यदि स्ट्रिंग की गणना की जाती है तो स्वीकार कर सकती है। इसके विपरीत, यदि कोई मशीन किसी भाषा में इनपुट होने पर स्वीकार करती है, तो दूसरी मशीन प्रत्येक इनपुट पर के सिमुलेशन को इंटरलीविंग करके और स्वीकार किए जाने वाले स्ट्रिंग्स को आउटपुट करके भाषा में सभी स्ट्रिंग्स की गणना कर सकती है (निष्पादन का एक क्रम है जो अंततः प्राप्त होगा प्रत्येक निष्पादन चरण क्योंकि इनपुट और चरणों के कई क्रमित जोड़े हैं)।
अन्य वर्गों से संबंध
पुनरावर्ती भाषाओं का समुच्चय (आर (जटिलता)) आरई और सह-आरई दोनों का एक सबसेट है।[3] वास्तव में यह उन दो वर्गों का प्रतिच्छेदन है क्योंकि हम किसी भी समस्या का निर्णय ले सकते हैं जिसके लिए एक पहचानकर्ता और एक सह-पहचानकर्ता उपस्थित है जब तक कि कोई परिणाम प्राप्त न हो जाए। इसलिए:
- .
इसके विपरीत भाषाओं का समूह जो न तो आरई है और न ही सह-आरई एनआरएनसी के रूप में जाना जाता है। ये भाषाओं का समूह हैं जिसके लिए न तो सदस्यता और न ही गैर-सदस्यता को सीमित समय में सिद्ध किया जा सकता है और इसमें अन्य सभी भाषाएँ सम्मिलित हैं जो आरई या सह-आरई में नहीं हैं। वह है:
- .
न केवल ये समस्याएं अनिर्णीत हैं किंतु न तो वे और न ही उनके पूरक पुनरावर्ती गणना योग्य हैं।
2020 के जनवरी में एक प्रीप्रिंट ने एक प्रमाण की घोषणा की कि आरई वर्ग एमआईपी * के समान था (वह वर्ग जहां एक मौलिक सत्यापनकर्ता कई सर्व-शक्तिशाली क्वांटम प्रोवर्स के साथ बातचीत करता है जो क्वांटम उलझाव साझा करते हैं);[4] एक संशोधित किंतु अभी तक पूरी तरह से समीक्षा नहीं की गई, प्रमाण नवंबर 2021 में एसीएम के संचार में प्रकाशित किया गया था। प्रमाण का अर्थ है कि कोन्स एम्बेडिंग समस्या और त्सिरेलसन की समस्या असत्य है।[5]
आरई-पूर्ण
आरई-पूर्ण निर्णय समस्याओं का समूह है जो आरई के लिए पूर्ण हैं। एक माध्यम में ये सबसे कठिन पुनरावर्ती गणना योग्य समस्याएं हैं। सामान्यतः उपयोग की जाने वाली कमी पर कोई प्रतिबंध नहीं लगाया जाता है अतिरिक्त इसके कि वे कई-एक कमी होनी चाहिए।
आरई-पूर्ण समस्याओं के उदाहरण:
- हॉल्टिंग की समस्या: क्या एक सीमित इनपुट दिया गया प्रोग्राम चलना समाप्त करता है या सदैव के लिए चलेगा।
- राइस के प्रमेय द्वारा संगणनीय कार्य के समुच्चय के किसी भी गैर-तुच्छ उपसमुच्चय में सदस्यता तय करना आरई-कठिन है। जब भी समुच्चय पुनरावर्ती रूप से गणनीय होगा, यह पूरा हो जाएगा।
- John Myhill (1955)[6] सिद्ध कर दिया कि सभी रचनात्मक समुच्चय आरई-पूर्ण हैं।
- समूह (गणित) या अर्धसमूहों के लिए समान शब्द समस्या (गणित)। (वास्तव में समूहों के लिए शब्द समस्या आरई-पूर्ण है।)
- एक सामान्य अप्रतिबंधित व्याकरण औपचारिक व्याकरण में सदस्यता तय करना। (फिर से कुछ व्यक्तिगत व्याकरणों में आरई-पूर्ण सदस्यता समस्याएँ हैं।)
- प्रथम क्रम तर्क के लिए वैधता (तर्क) समस्या।
- पोस्ट पत्राचार समस्या: तार के जोड़े की एक सूची को देखते हुए निर्धारित करें कि क्या इन जोड़ियों में से कोई चयन है (दोहराव की अनुमति) जैसे कि पहले आइटम (जोड़े के) का संयोजन दूसरे आइटम के संयोजन के समान है।
- यह निर्धारित करना कि डायोफैंटाइन समीकरण का कोई पूर्णांक समाधान है या नहीं।
सह-आरई-पूर्ण
सह-आरई-पूर्ण निर्णय समस्याओं का समूह है जो सह-आरई के लिए पूर्ण हैं। एक माध्यम में ये सबसे कठिन पुनरावर्ती गणना योग्य समस्याओं के पूरक हैं।
सह-आरई-पूर्ण समस्याओं के उदाहरण:
- वांग टाइल्स के लिए डोमिनोज़ समस्या।
- पहले क्रम के तर्क के लिए संतुष्टि की समस्या।
यह भी देखें
- नुथ-बेंडिक्स पूर्णता एल्गोरिथम
- अनिर्णीत समस्याओं की सूची
- बहुरूपी पुनरावर्तन
- रिस्क एल्गोरिथम
- निर्णायकता_(तर्क) या अर्ध-अम्लीयता
संदर्भ
- ↑ Complexity Zoo: Class RE
- ↑ Korfhage, Robert R. (1966). तर्क और एल्गोरिदम, कंप्यूटर और सूचना विज्ञान के अनुप्रयोगों के साथ. Wiley. p. 89.
A method of solution will be called a semi-algorithm for [a problem] P on [a device] M if the solution to P (if one exists) appears after the performance of finitely many steps. A semi-algorithm will be called an algorithm if, in addition, whenever the problem has no solution the method enables the device to determine this after a finite number of steps and halts.
- ↑ Complexity Zoo: Class co-RE
- ↑ Ji, Zhengfeng; Natarajan, Anand; Vidick, Thomas; Wright, John; Yuen, Henry (2020). "MIP*=RE". arXiv:2001.04383 [quant-ph].
- ↑ Ji, Zhengfeng; Natarajan, Anand; Vidick, Thomas; Wright, John; Yuen, Henry (November 2021). "MIP* = RE". Communications of the ACM. 64 (11): 131–138. doi:10.1145/3485628. S2CID 210165045.
- ↑ Myhill, John (1955), "Creative sets", Zeitschrift für Mathematische Logik und Grundlagen der Mathematik, 1 (2): 97–108, doi:10.1002/malq.19550010205, MR 0071379.
