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

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

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

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

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

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

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

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

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.

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