View source for आरई (जटिलता)

कम्प्यूटेबिलिटी सिद्धांत और [[कम्प्यूटेशनल जटिलता सिद्धांत]] में, आरई ([[पुनरावर्ती गणना योग्य सेट]]) [[निर्णय समस्या]]ओं की [[जटिलता वर्ग]] है, जिसके लिए एक 'हां' उत्तर को [[ट्यूरिंग मशीन]] द्वारा सीमित समय में सत्यापित किया जा सकता है।<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{NRNC} = \mbox{ALL} - (\mbox{RE}\cup\mbox{co-RE})</math>.

न केवल ये समस्याएं अनिर्णीत हैं, बल्कि न तो वे और न ही उनके पूरक पुनरावर्ती गणना योग्य हैं।

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 में ACM के संचार में प्रकाशित किया गया था। प्रमाण का अर्थ है कि Connes एम्बेडिंग समस्या और Tsirelson की समस्या झूठी है।<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
 | last = Myhill | first = John | authorlink = John Myhill
 | doi = 10.1002/malq.19550010205
 | journal = Zeitschrift für Mathematische Logik und Grundlagen der Mathematik
 | mr = 0071379
 | pages = 97–108
 | title = Creative sets
 | volume = 1
 | issue = 2 | year = 1955}}.</ref> साबित कर दिया कि सभी [[रचनात्मक सेट]] आरई-पूर्ण हैं।
# [[समूह (गणित)]] या अर्धसमूहों के लिए समान [[शब्द समस्या (गणित)]]। (वास्तव में, [[समूहों के लिए शब्द समस्या]] आरई-पूर्ण है।)
# एक सामान्य [[अप्रतिबंधित व्याकरण]] [[औपचारिक व्याकरण]] में सदस्यता तय करना। (फिर से, कुछ व्यक्तिगत व्याकरणों में RE-पूर्ण सदस्यता समस्याएँ हैं।)
# प्रथम क्रम तर्क के लिए [[वैधता (तर्क)]] समस्या।
# पोस्ट पत्राचार समस्या: तार के जोड़े की एक सूची को देखते हुए, निर्धारित करें कि क्या इन जोड़ियों में से कोई चयन है (दोहराव की अनुमति) जैसे कि पहले आइटम (जोड़े के) का संयोजन दूसरे आइटम के संयोजन के बराबर है।
# यह निर्धारित करना कि [[डायोफैंटाइन समीकरण]] का कोई पूर्णांक समाधान है या नहीं।

== सह-आरई-पूर्ण ==
सह-आरई-पूर्ण निर्णय समस्याओं का समूह है जो सह-आरई के लिए पूर्ण हैं। एक मायने में, ये सबसे कठिन पुनरावर्ती गणना योग्य समस्याओं के पूरक हैं।

सह-आरई-पूर्ण समस्याओं के उदाहरण:
#[[वांग टाइल्स]] के लिए [[डोमिनोज़ समस्या]]।
# पहले क्रम के तर्क के लिए [[संतुष्टि]] की समस्या।

== यह भी देखें ==
* नुथ-बेंडिक्स पूर्णता एल्गोरिथम
* [[अनिर्णीत समस्याओं की सूची]]
* [[बहुरूपी पुनरावर्तन]]
* [[रिस्क एल्गोरिथम]]
* निर्णायकता_(तर्क)#अर्ध-अम्लीयता

==संदर्भ==
<references/>

{{ComplexityClasses}}
[[Category: जटिलता वर्ग]] [[Category: अनिर्णीत समस्याएं]] 



[[Category: Machine Translated Page]]
[[Category:Created On 15/05/2023]]