यूपी (जटिलता): Difference between revisions
(Created page with "{{refimprove|date=August 2018}} कम्प्यूटेशनल जटिलता सिद्धांत में, यूपी (स्पष्ट गैर-न...") |
No edit summary |
||
| Line 1: | Line 1: | ||
{{refimprove|date=August 2018}} | {{refimprove|date=August 2018}} | ||
[[कम्प्यूटेशनल जटिलता सिद्धांत]] में | [[कम्प्यूटेशनल जटिलता सिद्धांत]] में UP (स्पष्ट गैर-निर्धारक बहुपद-समय) प्रत्येक इनपुट के लिए अधिकतम स्वीकार्य पथ के साथ स्पष्ट ट्यूरिंग मशीन पर बहुपद समय में हल करने योग्य [[निर्णय समस्या|निर्णय समस्याओं]] का [[जटिलता वर्ग]] है। UP में [[पी (जटिलता)|P (जटिलता)]] है और यह [[एनपी (जटिलता)|NP (जटिलता)]] में निहित है। | ||
NP के सामान्य सुधार में कहा गया है कि NP में एक भाषा है यदि और केवल यदि दिए गए उत्तर को बहुपद समय में नियतात्मक मशीन द्वारा सत्यापित किया जा सकता है। इसी प्रकार '''UP''' में एक भाषा है, यदि किसी दिए गए उत्तर को बहुपद समय में सत्यापित किया जा सकता है और सत्यापनकर्ता मशीन प्रत्येक समस्या उदाहरण के लिए अधिकतम 'एक' उत्तर स्वीकार करती है। अधिक औपचारिक रूप से ''L'' भाषा UP से संबंधित है यदि दो-इनपुट बहुपद-समय एल्गोरिदम ''A'' और स्थिरांक ''c'' उपस्थित है जैसे कि | |||
: यदि | : यदि ''L'' में x है तो एकमात्र प्रमाण ''y'' उपस्थित है तब <math>|y| = O(|x|^c)</math> ऐसा है {{tmath|1=A(x,y) = 1}} | ||
: यदि | : यदि L में x नहीं है तो कोई प्रमाण y उपस्थित नहीं है तब <math>|y| = O(|x|^c)</math> ऐसा है {{tmath|1=A(x,y) = 1}} | ||
: एल्गोरिदम | : एल्गोरिदम A बहुपद समय में L की पुष्टि करता है। | ||
' | '''UP''' (और इसके [[पूरक (जटिलता)]] 'को-UP') में [[पूर्णांक गुणनखंडन]] समस्या और [[समता खेल|पैरिटी गेम]] समस्या दोनों सम्मिलित हैं क्योंकि इन समस्याओं में से किसी भी समस्या का बहुपद-समय समाधान खोजने के लिए दृढ़ प्रयास अभी तक नहीं हुआ है, '''P = UP''' दिखाने में कठिनाई होने का संदेह है या यहां तक कि '''P = (UP ∩ co-UP)'''). | ||
वैलेंट-वजीरानी प्रमेय कहता है कि ' | वैलेंट-वजीरानी प्रमेय कहता है कि '''NP,''' '''RP<sup>प्रॉमिस-UP</sup>''' में समाहित है जिसका अर्थ है कि NP में किसी भी समस्या से [[ वादा समस्या |प्रॉमिस-UP समस्या]] में यादृच्छिक कमी है। | ||
'''UP''' में कोई [[पूर्ण (जटिलता)]] समस्या नहीं है।<ref>{{Cite web |title=में|url=https://complexityzoo.net/Complexity_Zoo:U#up |access-date= |website=[[Complexity Zoo]] |at=UP: Unambiguous Polynomial-Time}}</ref> | |||
==संदर्भ== | ==संदर्भ== | ||
Revision as of 23:26, 20 June 2023
 | This article needs additional citations for verification. (August 2018) (Learn how and when to remove this template message) |
कम्प्यूटेशनल जटिलता सिद्धांत में UP (स्पष्ट गैर-निर्धारक बहुपद-समय) प्रत्येक इनपुट के लिए अधिकतम स्वीकार्य पथ के साथ स्पष्ट ट्यूरिंग मशीन पर बहुपद समय में हल करने योग्य निर्णय समस्याओं का जटिलता वर्ग है। UP में P (जटिलता) है और यह NP (जटिलता) में निहित है।
NP के सामान्य सुधार में कहा गया है कि NP में एक भाषा है यदि और केवल यदि दिए गए उत्तर को बहुपद समय में नियतात्मक मशीन द्वारा सत्यापित किया जा सकता है। इसी प्रकार UP में एक भाषा है, यदि किसी दिए गए उत्तर को बहुपद समय में सत्यापित किया जा सकता है और सत्यापनकर्ता मशीन प्रत्येक समस्या उदाहरण के लिए अधिकतम 'एक' उत्तर स्वीकार करती है। अधिक औपचारिक रूप से L भाषा UP से संबंधित है यदि दो-इनपुट बहुपद-समय एल्गोरिदम A और स्थिरांक c उपस्थित है जैसे कि
- यदि L में x है तो एकमात्र प्रमाण y उपस्थित है तब ऐसा है
- यदि L में x नहीं है तो कोई प्रमाण y उपस्थित नहीं है तब ऐसा है
- एल्गोरिदम A बहुपद समय में L की पुष्टि करता है।
UP (और इसके पूरक (जटिलता) 'को-UP') में पूर्णांक गुणनखंडन समस्या और पैरिटी गेम समस्या दोनों सम्मिलित हैं क्योंकि इन समस्याओं में से किसी भी समस्या का बहुपद-समय समाधान खोजने के लिए दृढ़ प्रयास अभी तक नहीं हुआ है, P = UP दिखाने में कठिनाई होने का संदेह है या यहां तक कि P = (UP ∩ co-UP)).
वैलेंट-वजीरानी प्रमेय कहता है कि NP, RPप्रॉमिस-UP में समाहित है जिसका अर्थ है कि NP में किसी भी समस्या से प्रॉमिस-UP समस्या में यादृच्छिक कमी है।
UP में कोई पूर्ण (जटिलता) समस्या नहीं है।[1]
संदर्भ
उद्धरण
- ↑ "में". Complexity Zoo. UP: Unambiguous Polynomial-Time.
स्रोत
- Hemaspaandra, Lane A.; Rothe, Jörg (June 1997). "असंदिग्ध संगणना: बूलियन पदानुक्रम और विरल ट्यूरिंग-पूर्ण सेट". SIAM Journal on Computing (in English). 26 (3): 634–653. doi:10.1137/S0097539794261970. ISSN 0097-5397.
श्रेणी:जटिलता वर्ग
