यूपी (जटिलता)

कम्प्यूटेशनल जटिलता सिद्धांत में, यूपी (स्पष्ट गैर-नियतात्मक बहुपद-समय) प्रत्येक इनपुट के लिए अधिकतम एक स्वीकार्य पथ के साथ एक स्पष्ट ट्यूरिंग मशीन पर बहुपद समय में हल करने योग्य निर्णय समस्याओं का जटिलता वर्ग है। यूपी में पी (जटिलता) है और एनपी (जटिलता) में निहित है।

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

यदि x L में है, तो एक अद्वितीय प्रमाणपत्र y मौजूद है $|y|=O(|x|^{c})$ ऐसा है कि $A(x,y)=1$

यदि x L में नहीं है, तो कोई प्रमाणपत्र y नहीं है $|y|=O(|x|^{c})$ ऐसा है कि $A(x,y)=1$

एल्गोरिदम ए बहुपद समय में एल की पुष्टि करता है।

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

वैलेंट-वजीरानी प्रमेय कहता है कि 'एनपी' 'आरपी' में समाहित है^{प्रॉमिस-यूपी}, जिसका अर्थ है कि एनपी में किसी भी समस्या से वादा समस्या में एक यादृच्छिक कमी है। प्रॉमिस-यूपी।

उत्तर प्रदेश में कोई पूर्ण (जटिलता) समस्या नहीं है।

संदर्भ

स्रोत

• 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.

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