निर्णय समस्या

This article is about decision problems in complexity theory. For the decision problem in formal logic, see Entscheidungsproblem. For analysis of the process of making choices, see Decision theory.

एक निर्णय समस्या में किसी भी इनपुट पर केवल दो संभावित आउटपुट (हाँ या नहीं) होते हैं।

कम्प्यूटेबिलिटी सिद्धांत और कम्प्यूटेशनल जटिलता सिद्धांत में, एक निर्णय समस्या एक कम्प्यूटेशनल समस्या है जिसे इनपुट मूल्यों के हां-नहीं प्रश्न के रूप में प्रस्तुत किया जा सकता है। एक निर्णय समस्या का एक उदाहरण एक कलन विधि के माध्यम से निर्णय लेना है कि क्या दी गई प्राकृतिक संख्या अभाज्य संख्या है। एक और समस्या दो नंबर x और y दी गई है, क्या x समान रूप से y को विभाजित करता है? . 'x' और 'y' के मानों के आधार पर उत्तर या तो 'हां' या 'नहीं' है। एल्गोरिथम के रूप में दी गई निर्णय समस्या को हल करने की विधि को उस समस्या के लिए निर्णय प्रक्रिया कहा जाता है। निर्णय समस्या के लिए एक निर्णय प्रक्रिया दो संख्याएँ x और y दी गई है, क्या x समान रूप से y को विभाजित करती है? यह निर्धारित करने के लिए चरण देगा कि क्या x समान रूप से y को विभाजित करता है। ऐसा ही एक एल्गोरिथम लॉन्ग डिवीजन है। यदि शेषफल शून्य है तो उत्तर 'हाँ' है, अन्यथा 'नहीं' है। एक निर्णय समस्या जिसे एल्गोरिथम द्वारा हल किया जा सकता है, उसे 'निर्णायक' कहा जाता है।

निर्णय की समस्याएं आमतौर पर निर्णायकता (तर्क) के गणितीय प्रश्नों में दिखाई देती हैं, अर्थात, किसी वस्तु के अस्तित्व या किसी सेट में उसकी सदस्यता को निर्धारित करने के लिए एक प्रभावी विधि के अस्तित्व का प्रश्न; गणित की कुछ सबसे महत्वपूर्ण समस्याएँ अनिर्णीत समस्याएँ हैं।

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

परिभाषा

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

गोडेल नंबरिंग जैसे एन्कोडिंग का उपयोग करके, किसी भी स्ट्रिंग को प्राकृतिक संख्या के रूप में एन्कोड किया जा सकता है, जिसके माध्यम से एक निर्णय समस्या को प्राकृतिक संख्याओं के सबसेट के रूप में परिभाषित किया जा सकता है। इसलिए, निर्णय समस्या का एल्गोरिदम प्राकृतिक संख्याओं के सबसेट के संकेतक फ़ंक्शन की गणना करना है।

उदाहरण

निर्णायक निर्णय समस्या का एक उत्कृष्ट उदाहरण अभाज्य संख्याओं का समुच्चय है। प्रभावी रूप से यह तय करना संभव है कि क्या दी गई प्राकृतिक संख्या हर संभव गैर-कारक कारक का परीक्षण करके प्रमुख है। यद्यपि प्रारंभिक परीक्षण के बहुत अधिक कुशल तरीके ज्ञात हैं, किसी भी प्रभावी विधि का अस्तित्व निर्णायकता स्थापित करने के लिए पर्याप्त है।

निर्णायकता

Main articles: Undecidable problem and Decidability (logic)

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

रुकने की समस्या एक महत्वपूर्ण अनिर्णीत निर्णय समस्या है; अधिक उदाहरणों के लिए, अनिर्णीत समस्याओं की सूची देखें।

पूर्ण समस्याएं

Main article: Complete problem

निर्णय की समस्याओं को कई-एक कमी के अनुसार आदेशित किया जा सकता है | कई-एक रिड्यूसिबिलिटी और व्यवहार्य कटौती से संबंधित जैसे कि बहुपद-समय में कमी। एक निर्णय समस्या P को निर्णय समस्याओं के एक सेट के लिए पूर्ण समस्या कहा जाता है यदि P, S का सदस्य है और S में प्रत्येक समस्या को P तक कम किया जा सकता है। पूर्ण निर्णय समस्याओं का उपयोग कम्प्यूटेशनल जटिलता सिद्धांत में निर्णय की जटिलता वर्गों की विशेषता के लिए किया जाता है। समस्या। उदाहरण के लिए, बहुपद-समय रिड्यूसबिलिटी के तहत निर्णय समस्याओं के वर्ग एनपी (जटिलता) के लिए बूलियन संतुष्टि समस्या पूरी हो गई है।

समारोह की समस्याएं

Main article: Function problem

निर्णय की समस्याएं कार्यात्मक समस्याओं से निकटता से संबंधित हैं, जिनके उत्तर सरल 'हां' या 'नहीं' से अधिक जटिल हो सकते हैं। एक संगत समारोह की समस्या में दो नंबर x और y दिए गए हैं, x को y से डिवाइड करना क्या है? .

एक फ़ंक्शन समस्या में एक आंशिक फ़ंक्शन f होता है; अनौपचारिक समस्या उन इनपुटों पर f के मानों की गणना करना है जिनके लिए इसे परिभाषित किया गया है।

प्रत्येक कार्य समस्या को निर्णय समस्या में बदला जा सकता है; निर्णय समस्या केवल संबंधित फ़ंक्शन का ग्राफ़ है। (फ़ंक्शन f का ग्राफ़ जोड़े (x, y) का सेट है जैसे कि f(x) = y।) यदि यह निर्णय समस्या प्रभावी ढंग से हल करने योग्य थी तो फ़ंक्शन समस्या भी होगी। हालाँकि, यह कमी कम्प्यूटेशनल जटिलता का सम्मान नहीं करती है। उदाहरण के लिए, किसी फ़ंक्शन के ग्राफ़ के लिए बहुपद समय में निर्णायक होना संभव है (जिस स्थिति में चल रहे समय की गणना जोड़ी (x,y) के फ़ंक्शन के रूप में की जाती है) जब फ़ंक्शन बहुपद समय में गणना योग्य नहीं होता है (जिसमें केस चलने के समय की गणना केवल x के कार्य के रूप में की जाती है)। फलन f(x) = 2^x के पास यह गुण है।

निर्णय समस्या से जुड़े सेट के सूचक फ़ंक्शन की गणना करने की प्रत्येक निर्णय समस्या को फ़ंक्शन समस्या में परिवर्तित किया जा सकता है। यदि यह कार्य गणना योग्य है तो संबंधित निर्णय समस्या निर्णायक है। हालांकि, यह कमी कम्प्यूटेशनल जटिलता में उपयोग की जाने वाली मानक कमी की तुलना में अधिक उदार है (जिसे कभी-कभी बहुपद-समय कई-एक कमी कहा जाता है); उदाहरण के लिए, एक एनपी-पूर्ण समस्या और उसके सह-एनपी-पूर्ण पूरक (जटिलता) के विशिष्ट कार्यों की जटिलता बिल्कुल समान है, भले ही अंतर्निहित निर्णय समस्याओं को गणना के कुछ विशिष्ट मॉडल में समकक्ष नहीं माना जा सकता है।

अनुकूलन समस्याएं

Main article: Optimization problem

निर्णय समस्याओं के विपरीत, जिसके लिए प्रत्येक इनपुट के लिए केवल एक सही उत्तर होता है, अनुकूलन समस्याएँ किसी विशेष इनपुट के सर्वोत्तम उत्तर खोजने से संबंधित होती हैं। कई अनुप्रयोगों में अनुकूलन समस्याएं स्वाभाविक रूप से उत्पन्न होती हैं, जैसे ट्रैवलिंग सेल्समैन की समस्या और रैखिक प्रोग्रामिंग में कई प्रश्न।

कार्य और अनुकूलन समस्याओं को निर्णय समस्याओं में बदलने के लिए मानक तकनीकें हैं। उदाहरण के लिए, ट्रैवलिंग सेल्समैन समस्या में, अनुकूलन समस्या न्यूनतम वजन के साथ एक टूर तैयार करना है। संबंधित निर्णय समस्या है: प्रत्येक एन के लिए, यह तय करने के लिए कि ग्राफ में एन से कम वजन वाला कोई दौरा है या नहीं। निर्णय की समस्या का बार-बार उत्तर देकर, दौरे का न्यूनतम वजन खोजना संभव है।

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

यह भी देखें

• सभी (जटिलता)
• कम्प्यूटेशनल समस्या
• निर्णायकता (तर्क) - यह तय करने की समस्या के लिए कि क्या कोई सूत्र एक तार्किक सिद्धांत का परिणाम है।
• खोज समस्या
• गिनती की समस्या (जटिलता)
• शब्द समस्या (गणित)

संदर्भ

• Kozen, D.C. (2012). Automata and Computability. Springer. ISBN 9781461218449.
• Hartley, Rogers, Jr (1987). The Theory of Recursive Functions and Effective Computability. MIT Press. ISBN 9780262680523.{{cite book}}: CS1 maint: multiple names: authors list (link)
• Sipser, M. (2020). Introduction to the Theory of Computation. Cengage Learning. ISBN 9780357670583.
• Soare, Robert I. (1987). Recursively Enumerable Sets and Degrees. Springer. ISBN 0-387-15299-7.
• Kroening, Daniel; Strichman, Ofer (23 May 2008). Decision procedures. Springer. ISBN 978-3-540-74104-6.
• Bradley, Aaron; Manna, Zohar (3 September 2007). The calculus of computation. Springer. ISBN 978-3-540-74112-1.