निर्णय समस्या: Difference between revisions

From Vigyanwiki
(Created page with "{{short description|Yes/no problem in computer science}} {{about|decision problems in complexity theory|the decision problem in formal logic|Entscheidungsproblem|analysis of t...")
 
No edit summary
Line 1: Line 1:
{{short description|Yes/no problem in computer science}}
{{short description|Yes/no problem in computer science}}
{{about|decision problems in complexity theory|the decision problem in formal logic|Entscheidungsproblem|analysis of the process of making choices|Decision theory}}
{{about|यह लेख जटिलता सिद्धांत में निर्णय समस्याओं के बारे में है।|औपचारिक तर्क में निर्णय की समस्या के लिए|Entscheidungs समस्या देखें।|चुनाव करने की प्रक्रिया के विश्लेषण के लिए|निर्णय सिद्धांत देखें।}}
[[Image:Decision Problem.svg|thumb|200px|एक निर्णय समस्या में किसी भी इनपुट पर केवल दो संभावित आउटपुट (हाँ या नहीं) होते हैं।]]कम्प्यूटेबिलिटी सिद्धांत और [[कम्प्यूटेशनल जटिलता सिद्धांत]] में, एक निर्णय समस्या एक कम्प्यूटेशनल समस्या है जिसे इनपुट मूल्यों के हां-नहीं प्रश्न के रूप में प्रस्तुत किया जा सकता है। एक निर्णय समस्या का एक उदाहरण एक [[कलन विधि]] के माध्यम से निर्णय लेना है कि क्या दी गई प्राकृतिक संख्या [[अभाज्य संख्या]] है। एक और समस्या दो नंबर '' x '' और '' y '' दी गई है, क्या '' x '' समान रूप से '' y '' को विभाजित करता है? . 'x' और 'y' के मानों के आधार पर उत्तर या तो 'हां' या 'नहीं' है। एल्गोरिथम के रूप में दी गई निर्णय समस्या को हल करने की विधि को उस समस्या के लिए निर्णय प्रक्रिया कहा जाता है। निर्णय समस्या के लिए एक निर्णय प्रक्रिया दो संख्याएँ ''x'' और ''y'' दी गई है, क्या ''x'' समान रूप से ''y'' को विभाजित करती है? यह निर्धारित करने के लिए चरण देगा कि क्या ''x'' समान रूप से ''y'' को विभाजित करता है। ऐसा ही एक एल्गोरिथम लॉन्ग डिवीजन है। यदि शेषफल शून्य है तो उत्तर 'हाँ' है, अन्यथा 'नहीं' है। एक निर्णय समस्या जिसे एल्गोरिथम द्वारा हल किया जा सकता है, उसे 'निर्णायक' कहा जाता है।
[[Image:Decision Problem.svg|thumb|200px|एक निर्णय समस्या में किसी भी निवेश पर केवल दो संभावित उत्पाद (हाँ या नहीं) होते हैं।]]अभिकलनीयता सिद्धांत और [[कम्प्यूटेशनल जटिलता सिद्धांत|अभिकलनीय प्रणाली जटिलता सिद्धांत]] में, निर्णय समस्या एक ऐसी  संगणनात्मक समस्या है जिसे निवेश मूल्यों के सही - गलत प्रश्न के रूप में प्रस्तुत किया जाता है। निर्णय समस्या का उदाहरण एक [[कलन विधि]] के माध्यम से निर्णय लेना है कि क्या दी गई प्राकृतिक संख्या [[अभाज्य संख्या]] है? एक और समस्या दो नंबर '' x '' और '' y '' दी गई है, क्या '' x '' समान रूप से '' y '' को विभाजित करता है? . 'x' और 'y' के मानों के आधार पर उत्तर 'हां' या 'नहीं' है। कलनविधि के रूप में दी गई निर्णय समस्या को हल करने की विधि को उस समस्या के लिए निर्णय प्रक्रिया कहा जाता है। निर्णय समस्या के लिए एक निर्णय प्रक्रिया दो संख्याएँ ''x'' और ''y'' दी गई है, क्या ''x'' समान रूप से ''y'' को विभाजित करती है? यह निर्धारित करने के लिए चरण देगा कि क्या ''x'' समान रूप से ''y'' को विभाजित करता है। ऐसा ही एक कलनविधि लॉन्ग डिवीजन है। यदि शेषफल शून्य है तो उत्तर 'हाँ' है, अन्यथा 'नहीं' है। एक निर्णय समस्या जिसे कलनविधि द्वारा हल किया जा सकता है, उसे 'निर्णायक' कहा जाता है।


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


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


== परिभाषा ==
== परिभाषा ==
एक निर्णय समस्या इनपुट के [[अनंत सेट]] पर हां या नहीं का प्रश्न है। निर्णय समस्या को संभावित इनपुट के सेट के साथ-साथ इनपुट के सेट के रूप में परिभाषित करना पारंपरिक है, जिसका उत्तर हां है।<ref>{{cite web|url=https://www.cs.stanford.edu/~trevisan/cs254-10/lecture02.pdf |archive-url=https://web.archive.org/web/20151010023326/http://www.cs.stanford.edu/~trevisan/cs254-10/lecture02.pdf |archive-date=2015-10-10 |url-status=live|title=CS254: Computational Complexity: Lecture 2}}</ref>
एक निर्णय समस्या निवेश के [[अनंत सेट|अनंत समुच्चय]] पर हां या नहीं का प्रश्न है। निर्णय समस्या को संभावित निवेश के समुच्चय के साथ-साथ निवेश के समुच्चय के रूप में परिभाषित करना पारंपरिक है, जिसका उत्तर हां है।<ref>{{cite web|url=https://www.cs.stanford.edu/~trevisan/cs254-10/lecture02.pdf |archive-url=https://web.archive.org/web/20151010023326/http://www.cs.stanford.edu/~trevisan/cs254-10/lecture02.pdf |archive-date=2015-10-10 |url-status=live|title=CS254: Computational Complexity: Lecture 2}}</ref>
ये इनपुट प्राकृतिक संख्या हो सकते हैं, लेकिन कुछ अन्य प्रकार के मान भी हो सकते हैं, जैसे बाइनरी [[स्ट्रिंग (कंप्यूटर विज्ञान)]] या किसी अन्य [[वर्णमाला (कंप्यूटर विज्ञान)]] पर तार। स्ट्रिंग्स का सबसेट जिसके लिए समस्या हां लौटाती है एक [[औपचारिक भाषा]] है, और अक्सर निर्णय समस्याओं को औपचारिक भाषाओं के रूप में परिभाषित किया जाता है।
ये निवेश प्राकृतिक संख्या हो सकती है, लेकिन कुछ अन्य प्रकार के मान भी हो सकते हैं, जैसे युग्मक [[स्ट्रिंग (कंप्यूटर विज्ञान)|गणनीय संज्ञा (कंप्यूटर विज्ञान)]] या किसी अन्य [[वर्णमाला (कंप्यूटर विज्ञान)]]। गणनीय संज्ञा का उपसमुच्चय जिसके लिए समस्या हां निर्गत करती है एक [[औपचारिक भाषा]] है, और अधिकांशतः निर्णय समस्याओं को औपचारिक भाषाओं के रूप में परिभाषित किया जाता है।


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


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


== निर्णायकता ==
== निर्णायकता ==


{{main|Undecidable problem|Decidability (logic)}}
{{main|मुख्य लेख: अनिर्णीत समस्या और|निर्णायकता (तर्क)}}
एक निर्णय समस्या निर्णायक या प्रभावी रूप से हल करने योग्य है यदि इनपुट का सेट (या प्राकृतिक संख्या) जिसके लिए उत्तर हाँ है, एक [[पुनरावर्ती सेट]] है। एक समस्या आंशिक रूप से निर्णायक, अर्ध-निर्णायक, हल करने योग्य, या साबित करने योग्य है यदि इनपुट का सेट (या प्राकृतिक संख्या) जिसके लिए उत्तर हाँ है, एक [[पुनरावर्ती गणना योग्य सेट]] है। समस्याएँ जो निर्णायक नहीं हैं वे अनिर्णीत हैं। उन लोगों के लिए एक एल्गोरिथम बनाना संभव नहीं है, कुशल या अन्यथा, जो उन्हें हल करता है।


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


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


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


== समारोह की समस्याएं ==
== समारोह की समस्याएं ==
{{main|Function problem}}
{{main|मुख्य लेख: कार्यात्मक समस्या}}
निर्णय की समस्याएं कार्यात्मक समस्याओं से निकटता से संबंधित हैं, जिनके उत्तर सरल 'हां' या 'नहीं' से अधिक जटिल हो सकते हैं। एक संगत [[समारोह की समस्या]] में दो नंबर x और y दिए गए हैं, x को y से डिवाइड करना क्या है? .
निर्णय की समस्याएं कार्यात्मक समस्याओं से निकटता से संबंधित हैं, जिनके उत्तर सरल 'हां' या 'नहीं' से अधिक जटिल हो सकते हैं। एक संगत [[समारोह की समस्या]] में दो नंबर x और y दिए गए हैं, x को y से भाग देना क्या है? .


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


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


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


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


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


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


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

Revision as of 19:22, 12 February 2023

This article is about यह लेख जटिलता सिद्धांत में निर्णय समस्याओं के बारे में है।. For औपचारिक तर्क में निर्णय की समस्या के लिए, see Entscheidungs समस्या देखें।. For चुनाव करने की प्रक्रिया के विश्लेषण के लिए, see निर्णय सिद्धांत देखें।.
एक निर्णय समस्या में किसी भी निवेश पर केवल दो संभावित उत्पाद (हाँ या नहीं) होते हैं।

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

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

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

परिभाषा

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

गोडेल नंबरिंग जैसे संकेतन का उपयोग करके, किसी भी गणनीय संज्ञा को प्राकृतिक संख्या के रूप में संकेतन किया जा सकता है, जिसके माध्यम से एक निर्णय समस्या को प्राकृतिक संख्याओं के उपसमुच्चय के रूप में परिभाषित किया जा सकता है। इसलिए, निर्णय समस्या का कलनविधि प्राकृतिक संख्याओं के उपसमुच्चय के संकेतक क्रिया की गणना करना है।

उदाहरण

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

निर्णायकता

Main articles: मुख्य लेख: अनिर्णीत समस्या और and निर्णायकता (तर्क)

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

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

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

Main article: मुख्य लेख: पूरी समस्या

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

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

Main article: मुख्य लेख: कार्यात्मक समस्या

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

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

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

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

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

Main article: मुख्य लेख: अनुकूलन समस्या

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

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

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

यह भी देखें

संदर्भ

  • 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.
  1. ↑ "CS254: Computational Complexity: Lecture 2" (PDF). Archived (PDF) from the original on 2015-10-10.
Retrieved from ‘https://www.vigyanwiki.in/index.php?title=निर्णय_समस्या&oldid=86647’