यूपी (जटिलता): Difference between revisions

From Vigyanwiki
(Created page with "{{refimprove|date=August 2018}} कम्प्यूटेशनल जटिलता सिद्धांत में, यूपी (स्पष्ट गैर-न...")
 
No edit summary
 
(3 intermediate revisions by 3 users not shown)
Line 1: Line 1:
{{refimprove|date=August 2018}}
{{refimprove|date=August 2018}}
[[कम्प्यूटेशनल जटिलता सिद्धांत]] में, यूपी (स्पष्ट गैर-नियतात्मक बहुपद-समय) प्रत्येक इनपुट के लिए अधिकतम एक स्वीकार्य पथ के साथ एक स्पष्ट ट्यूरिंग मशीन पर बहुपद समय में हल करने योग्य [[निर्णय समस्या]]ओं का [[जटिलता वर्ग]] है। यूपी में [[पी (जटिलता)]] है और [[एनपी (जटिलता)]] में निहित है।
[[कम्प्यूटेशनल जटिलता सिद्धांत]] में UP (स्पष्ट गैर-निर्धारक बहुपद-समय) प्रत्येक इनपुट के लिए अधिकतम स्वीकार्य पथ के साथ स्पष्ट ट्यूरिंग मशीन पर बहुपद समय में हल करने योग्य [[निर्णय समस्या|निर्णय समस्याओं]] का [[जटिलता वर्ग]] है। UP में [[पी (जटिलता)|P (जटिलता)]] है और यह [[एनपी (जटिलता)|NP (जटिलता)]] में निहित है।


एनपी के एक सामान्य सुधार में कहा गया है कि एक भाषा एनपी में है अगर और केवल अगर दिए गए उत्तर को बहुपद समय में नियतात्मक मशीन द्वारा सत्यापित किया जा सकता है। इसी तरह, एक भाषा उत्तर प्रदेश में है यदि किसी दिए गए उत्तर को बहुपद समय में सत्यापित किया जा सकता है, और सत्यापनकर्ता मशीन प्रत्येक समस्या उदाहरण के लिए अधिकतम 'एक' उत्तर स्वीकार करती है। अधिक औपचारिक रूप से, एक भाषा ''एल'' यूपी से संबंधित है यदि दो-इनपुट बहुपद-समय एल्गोरिदम '''' और एक स्थिर ''सी'' मौजूद है जैसे कि
NP के सामान्य सुधार में कहा गया है कि NP में एक भाषा है यदि और केवल यदि दिए गए उत्तर को बहुपद समय में नियतात्मक मशीन द्वारा सत्यापित किया जा सकता है। इसी प्रकार '''UP''' में एक भाषा है, यदि किसी दिए गए उत्तर को बहुपद समय में सत्यापित किया जा सकता है और सत्यापनकर्ता मशीन प्रत्येक समस्या उदाहरण के लिए अधिकतम 'एक' उत्तर स्वीकार करती है। अधिक औपचारिक रूप से ''L'' भाषा UP से संबंधित है यदि दो-इनपुट बहुपद-समय एल्गोरिदम ''A'' और स्थिरांक ''c'' उपस्थित है जैसे कि
: यदि x ''L'' में है, तो एक अद्वितीय प्रमाणपत्र ''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}}
: यदि x L में नहीं है, तो कोई प्रमाणपत्र y नहीं है <math>|y| = O(|x|^c)</math> ऐसा है कि {{tmath|1=A(x,y) = 1}}
: यदि L में नहीं है तो कोई प्रमाण y उपस्थित नहीं है तब <math>|y| = O(|x|^c)</math> ऐसा है {{tmath|1=A(x,y) = 1}}
: एल्गोरिदम बहुपद समय में एल की पुष्टि करता है।
: एल्गोरिदम A बहुपद समय में L की पुष्टि करता है।


'यूपी' (और इसके [[पूरक (जटिलता)]] 'को-यूपी') में [[पूर्णांक गुणनखंडन]] समस्या और [[समता खेल]] समस्या दोनों शामिल हैं; क्योंकि इनमें से किसी भी समस्या का बहुपद-समय समाधान खोजने के लिए दृढ़ प्रयास अभी तक नहीं हुआ है, इसलिए 'P' = 'UP', या यहां तक ​​कि 'P' = ('UP' 'co-UP' दिखाना मुश्किल होने का संदेह है) ).
'''UP''' (और इसके [[पूरक (जटिलता)]] 'को-UP') में [[पूर्णांक गुणनखंडन]] समस्या और [[समता खेल|पैरिटी गेम]] समस्या दोनों सम्मिलित हैं क्योंकि इन समस्याओं में से किसी भी समस्या का बहुपद-समय समाधान खोजने के लिए दृढ़ प्रयास अभी तक नहीं हुआ है, '''P = UP''' दिखाने में कठिनाई होने का संदेह है या यहां तक ​​कि '''P = (UP ∩ co-UP)''').


वैलेंट-वजीरानी प्रमेय कहता है कि 'एनपी' 'आरपी' में समाहित है<sup>प्रॉमिस-यूपी</sup>, जिसका अर्थ है कि एनपी में किसी भी समस्या से [[ वादा समस्या ]] में एक यादृच्छिक कमी है। प्रॉमिस-यूपी।
वैलेंट-वजीरानी प्रमेय कहता है कि '''NP,''' '''RP<sup>प्रॉमिस-UP</sup>''' में समाहित है जिसका अर्थ है कि NP में किसी भी समस्या से [[ वादा समस्या |प्रॉमिस-UP समस्या]] में यादृच्छिक कमी है।
 
उत्तर प्रदेश में कोई [[पूर्ण (जटिलता)]] समस्या नहीं है।<ref>{{Cite web |title=में|url=https://complexityzoo.net/Complexity_Zoo:U#up |access-date= |website=[[Complexity Zoo]] |at=UP: Unambiguous Polynomial-Time}}</ref>


'''UP''' में कोई [[पूर्ण (जटिलता)]] समस्या नहीं है।<ref>{{Cite web |title=में|url=https://complexityzoo.net/Complexity_Zoo:U#up |access-date= |website=[[Complexity Zoo]] |at=UP: Unambiguous Polynomial-Time}}</ref>


==संदर्भ==
==संदर्भ==
Line 29: Line 28:
श्रेणी:जटिलता वर्ग
श्रेणी:जटिलता वर्ग


 
[[Category:All articles needing additional references]]
[[Category: Machine Translated Page]]
[[Category:Articles needing additional references from August 2018]]
[[Category:CS1 English-language sources (en)]]
[[Category:Collapse templates]]
[[Category:Created On 08/06/2023]]
[[Category:Created On 08/06/2023]]
[[Category:Machine Translated Page]]
[[Category:Navigational boxes| ]]
[[Category:Navigational boxes without horizontal lists]]
[[Category:Pages with script errors]]
[[Category:Sidebars with styles needing conversion]]
[[Category:Template documentation pages|Documentation/doc]]
[[Category:Templates Vigyan Ready]]
[[Category:Templates generating microformats]]
[[Category:Templates that are not mobile friendly]]
[[Category:Templates using TemplateData]]
[[Category:Wikipedia metatemplates]]

Latest revision as of 09:45, 28 June 2023

कम्प्यूटेशनल जटिलता सिद्धांत में 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]

संदर्भ

उद्धरण

  1. "में". Complexity Zoo. UP: Unambiguous Polynomial-Time.


स्रोत

श्रेणी:जटिलता वर्ग