निर्णय समस्या: Difference between revisions
No edit summary |
No edit summary |
||
| Line 1: | Line 1: | ||
{{short description|Yes/no problem in computer science}} | {{short description|Yes/no problem in computer science}} | ||
{{about|यह लेख जटिलता सिद्धांत में निर्णय समस्याओं के बारे में है।|औपचारिक तर्क में निर्णय की समस्या के लिए|Entscheidungs समस्या देखें।|चुनाव करने की प्रक्रिया के विश्लेषण के लिए|निर्णय सिद्धांत देखें।}} | {{about|यह लेख जटिलता सिद्धांत में निर्णय समस्याओं के बारे में है।|औपचारिक तर्क में निर्णय की समस्या के लिए|Entscheidungs समस्या देखें।|चुनाव करने की प्रक्रिया के विश्लेषण के लिए|निर्णय सिद्धांत देखें।}} | ||
[[Image:Decision Problem.svg|thumb|200px|एक निर्णय समस्या में किसी भी निवेश पर केवल दो संभावित उत्पाद (हाँ या नहीं) होते हैं।]]अभिकलनीयता सिद्धांत और [[कम्प्यूटेशनल जटिलता सिद्धांत|अभिकलनीय प्रणाली जटिलता सिद्धांत]] में | [[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> | |||
ये निवेश प्राकृतिक संख्या हो सकती है, लेकिन कुछ अन्य प्रकार के मान भी हो सकते हैं, जैसे युग्मक [[स्ट्रिंग (कंप्यूटर विज्ञान)|गणनीय संज्ञा (कंप्यूटर विज्ञान)]] या किसी अन्य [[वर्णमाला (कंप्यूटर विज्ञान)]]। गणनीय संज्ञा का उपसमुच्चय जिसके लिए समस्या हां निर्गत करती | ये निवेश प्राकृतिक संख्या हो सकती है, लेकिन कुछ अन्य प्रकार के मान भी हो सकते हैं, जैसे युग्मक [[स्ट्रिंग (कंप्यूटर विज्ञान)|गणनीय संज्ञा (कंप्यूटर विज्ञान)]] या किसी अन्य [[वर्णमाला (कंप्यूटर विज्ञान)]]। गणनीय संज्ञा का उपसमुच्चय जिसके लिए समस्या हां निर्गत करती [[औपचारिक भाषा]] है, और अधिकांशतः निर्णय समस्याओं को औपचारिक भाषाओं के रूप में परिभाषित किया जाता है। | ||
गोडेल नंबरिंग जैसे संकेतन का उपयोग करके, किसी भी गणनीय संज्ञा को प्राकृतिक संख्या के रूप में संकेतन किया जा सकता है, जिसके माध्यम से | गोडेल नंबरिंग जैसे संकेतन का उपयोग करके, किसी भी गणनीय संज्ञा को प्राकृतिक संख्या के रूप में संकेतन किया जा सकता है, जिसके माध्यम से निर्णय समस्या को प्राकृतिक संख्याओं के उपसमुच्चय के रूप में परिभाषित किया जा सकता है। इसलिए, निर्णय समस्या का कलनविधि प्राकृतिक संख्याओं के उपसमुच्चय के संकेतक क्रिया की गणना करना है। | ||
== उदाहरण == | == उदाहरण == | ||
निर्णायक निर्णय समस्या का | निर्णायक निर्णय समस्या का उत्कृष्ट उदाहरण अभाज्य संख्याओं का समुच्चय है। प्रभावी रूप से यह तय करना संभव है कि क्या दी गई प्राकृतिक संख्या हर संभव गैर-कारक के परीक्षण में प्रमुख है। यद्यपि [[प्रारंभिक परीक्षण]] के बहुत अधिक कुशल तरीके ज्ञात हैं, किसी भी प्रभावी विधि का अस्तित्व निर्णायकता स्थापित करने के लिए पर्याप्त है। | ||
== निर्णायकता == | == निर्णायकता == | ||
| Line 20: | Line 20: | ||
{{main|मुख्य लेख: अनिर्णीत समस्या और|निर्णायकता (तर्क)}} | {{main|मुख्य लेख: अनिर्णीत समस्या और|निर्णायकता (तर्क)}} | ||
निर्णय समस्या निर्णायक या प्रभावी रूप से हल करने योग्य है यदि निवेश का समुच्चय (या प्राकृतिक संख्या) जिसके लिए उत्तर हाँ है, एक [[पुनरावर्ती सेट|पुनरावर्ती]] समुच्चय है। समस्या आंशिक रूप से निर्णायक, अर्ध-निर्णायक, हल करने योग्य, या साबित करने योग्य है यदि निवेश का समुच्चय (या प्राकृतिक संख्या) जिसके लिए उत्तर हाँ है, [[पुनरावर्ती गणना योग्य सेट|पुनरावर्ती गणना योग्य]] समुच्चय है। समस्याएँ जो निर्णायक नहीं हैं वे अनिर्णीत हैं। उन लोगों के लिए कलनविधि बनाना संभव नहीं है, कुशल या अन्यथा, जो उन्हें हल कर सकता है। | |||
[[रुकने की समस्या|हाल्टिंग की समस्या]] | [[रुकने की समस्या|हाल्टिंग की समस्या]] महत्वपूर्ण अनिर्णीत निर्णय समस्या है; अधिक उदाहरणों के लिए, [[अनिर्णीत समस्याओं की सूची]] देखें। | ||
== पूर्ण समस्याएं == | == पूर्ण समस्याएं == | ||
| Line 28: | Line 28: | ||
{{main|मुख्य लेख: पूरी समस्या}} | {{main|मुख्य लेख: पूरी समस्या}} | ||
निर्णय की समस्याओं को कई कमी के अनुसार आदेशित किया | निर्णय की समस्याओं को कई कमी के अनुसार आदेशित किया जाता है | कई समानेयता और व्यवहार्य कटौती से संबंधित जैसे कि [[बहुपद-समय में कमी]] है। निर्णय समस्या P को निर्णय समस्याओं के एक समुच्चय के लिए पूर्ण समस्या कहा जाता है यदि P, S का सदस्य है और S में प्रत्येक समस्या को P तक कम किया जा सकता है। पूर्ण निर्णय समस्याओं का उपयोग संगणनात्मक जटिलता सिद्धांत में निर्णय की [[जटिलता वर्ग]]ों की विशेषता के लिए किया जाता है। समस्या उदाहरण के लिए, बहुपद-समय समानेयताके अनुसार निर्णय समस्याओं के वर्ग [[एनपी (जटिलता)]] के लिए [[बूलियन संतुष्टि समस्या]] पूरी करी गई है। | ||
== समारोह की समस्याएं == | == समारोह की समस्याएं == | ||
{{main|मुख्य लेख: कार्यात्मक समस्या}} | {{main|मुख्य लेख: कार्यात्मक समस्या}} | ||
निर्णय की समस्याएं कार्यात्मक समस्याओं से निकटता से संबंधित हैं, जिनके उत्तर सरल 'हां' या 'नहीं' से अधिक जटिल हो सकते हैं। | निर्णय की समस्याएं कार्यात्मक समस्याओं से निकटता से संबंधित हैं, जिनके उत्तर सरल 'हां' या 'नहीं' से अधिक जटिल हो सकते हैं। संगत [[समारोह की समस्या]] में दो नंबर x और y दिए गए हैं, x को y से भाग देना क्या है? . | ||
क्रिया समस्या में आंशिक क्रिया 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|मुख्य लेख: अनुकूलन समस्या}} | {{main|मुख्य लेख: अनुकूलन समस्या}} | ||
निर्णय समस्याओं के विपरीत, जिसके लिए प्रत्येक निवेश के लिए केवल एक सही उत्तर होता है, अनुकूलन समस्याएँ किसी विशेष निवेश के सर्वोत्तम उत्तर खोजने से संबंधित होती हैं। कई अनुप्रयोगों में अनुकूलन समस्याएं स्वाभाविक रूप से उत्पन्न होती हैं, जैसे [[ट्रैवलिंग सेल्समैन की समस्या]] और [[रैखिक प्रोग्रामिंग]] | निर्णय समस्याओं के विपरीत, जिसके लिए प्रत्येक निवेश के लिए केवल एक सही उत्तर होता है, अनुकूलन समस्याएँ किसी विशेष निवेश के सर्वोत्तम उत्तर खोजने से संबंधित होती हैं। कई अनुप्रयोगों में अनुकूलन समस्याएं स्वाभाविक रूप से उत्पन्न होती हैं, जैसे [[ट्रैवलिंग सेल्समैन की समस्या]] और [[रैखिक प्रोग्रामिंग]] के प्रश्न। | ||
कार्य और अनुकूलन समस्याओं को निर्णय समस्याओं में बदलने के लिए मानक तकनीकें हैं। उदाहरण के लिए, ट्रैवलिंग सेल्समैन समस्या में, अनुकूलन समस्या न्यूनतम वजन के साथ | कार्य और अनुकूलन समस्याओं को निर्णय समस्याओं में बदलने के लिए मानक तकनीकें हैं। उदाहरण के लिए, ट्रैवलिंग सेल्समैन समस्या में, अनुकूलन समस्या न्यूनतम वजन के साथ परिक्रम तैयार करना है। संबंधित निर्णय समस्या है: प्रत्येक एन के लिए, यह तय करने के लिए कि लेखाचित्र में एन से कम वजन वाला कोई दौरा है या नहीं। निर्णय की समस्या का बार-बार उत्तर देकर, दौरे का न्यूनतम वजन खोजना संभव है। | ||
क्योंकि निर्णय समस्याओं का सिद्धांत बहुत अच्छे प्रकार से विकसित है, जटिलता सिद्धांत में अनुसंधान ने विशेष रूप से निर्णय समस्याओं पर ध्यान केंद्रित किया है। अनुकूलन की समस्याएं अभी भी संगणनीयता सिद्धांत के साथ-साथ संचालन अनुसंधान जैसे क्षेत्रों में रुचि रखती हैं। | क्योंकि निर्णय समस्याओं का सिद्धांत बहुत अच्छे प्रकार से विकसित है, जटिलता सिद्धांत में अनुसंधान ने विशेष रूप से निर्णय समस्याओं पर ध्यान केंद्रित किया है। अनुकूलन की समस्याएं अभी भी संगणनीयता सिद्धांत के साथ-साथ संचालन अनुसंधान जैसे क्षेत्रों में रुचि रखती हैं। | ||
| Line 52: | Line 52: | ||
* [[सभी (जटिलता)]] | * [[सभी (जटिलता)]] | ||
* [[कम्प्यूटेशनल समस्या|संगणनात्मक समस्या]] | * [[कम्प्यूटेशनल समस्या|संगणनात्मक समस्या]] | ||
* निर्णायकता (तर्क) - यह तय करने की समस्या के लिए कि क्या कोई सूत्र | * निर्णायकता (तर्क) - यह तय करने की समस्या के लिए कि क्या कोई सूत्र [[तार्किक सिद्धांत]] का परिणाम है। | ||
* [[खोज समस्या]] | * [[खोज समस्या]] | ||
* [[गिनती की समस्या (जटिलता)]] | * [[गिनती की समस्या (जटिलता)]] | ||
Revision as of 22:46, 13 February 2023
अभिकलनीयता सिद्धांत और अभिकलनीय प्रणाली जटिलता सिद्धांत में निर्णय समस्या एक ऐसी संगणनात्मक समस्या है जिसे निवेश मूल्यों के सही - गलत प्रश्न के रूप में प्रस्तुत किया जाता है। निर्णय समस्या का उदाहरण कलन विधि के माध्यम से निर्णय लेना है कि क्या दी गई प्राकृतिक संख्या अभाज्य संख्या है या नहीं। एक और समस्या दो नंबर x और y दी गई है, क्या x समान रूप से y को विभाजित करता है। 'x' और 'y' के मानों के आधार पर उत्तर 'हां' या 'नहीं' है। कलनविधि के रूप में दी गई निर्णय समस्या को हल करने की विधि को उस समस्या के लिए निर्णय प्रक्रिया कहा जाता है। निर्णय समस्या के लिए निर्णय प्रक्रिया दो संख्याएँ x और y दी गई है, क्या x समान रूप से y को विभाजित करती है। यह निर्धारित करने के लिए चरण देगा कि क्या x समान रूप से y को विभाजित करता है। ऐसा ही कलनविधि लॉन्ग डिवीजन है। यदि शेषफल शून्य है तो उत्तर 'हाँ' है, अन्यथा 'नहीं' है। निर्णय समस्या जिसे कलनविधि द्वारा हल किया जा सकता है, उसे 'निर्णायक' कहा जाता है।
निर्णय की समस्याएं सामान्यतः निर्णायकता (तर्क) के गणितीय प्रश्नों में दिखाई देती हैं, अर्थात, किसी वस्तु के अस्तित्व या किसी समुच्चय में उसकी सदस्यता को निर्धारित करने के लिए प्रभावी विधि के अस्तित्व का प्रश्न; गणित की कुछ सबसे महत्वपूर्ण समस्याएँ अनिर्णीत समस्याएँ हैं।
अभिकलनीयता जटिलता का क्षेत्र 'निर्णायक' निर्णय समस्याओं को इस आधार पर वर्गीकृत करता है कि उन्हें हल करना कितना कठिन है। कठिन, इस अर्थ में, निश्चित समस्या के लिए सबसे कुशल कलनविधि द्वारा आवश्यक संगणनात्मक संसाधनों के संदर्भ में वर्णित है। पुनरावर्तन सिद्धांत का क्षेत्र, इस बीच, ट्यूरिंग डिग्री द्वारा 'अनिश्चित' निर्णय समस्याओं को वर्गीकृत करता है, जो किसी भी समाधान में निहित गैर-अभिकलनीयता का एक माध्यम है।
परिभाषा
निर्णय समस्या निवेश के अनंत समुच्चय पर हां या नहीं का प्रश्न है। निर्णय समस्या को संभावित निवेश के समुच्चय के साथ-साथ निवेश के समुच्चय के रूप में परिभाषित करना पारंपरिक है, जिसका उत्तर हां है।[1] ये निवेश प्राकृतिक संख्या हो सकती है, लेकिन कुछ अन्य प्रकार के मान भी हो सकते हैं, जैसे युग्मक गणनीय संज्ञा (कंप्यूटर विज्ञान) या किसी अन्य वर्णमाला (कंप्यूटर विज्ञान)। गणनीय संज्ञा का उपसमुच्चय जिसके लिए समस्या हां निर्गत करती औपचारिक भाषा है, और अधिकांशतः निर्णय समस्याओं को औपचारिक भाषाओं के रूप में परिभाषित किया जाता है।
गोडेल नंबरिंग जैसे संकेतन का उपयोग करके, किसी भी गणनीय संज्ञा को प्राकृतिक संख्या के रूप में संकेतन किया जा सकता है, जिसके माध्यम से निर्णय समस्या को प्राकृतिक संख्याओं के उपसमुच्चय के रूप में परिभाषित किया जा सकता है। इसलिए, निर्णय समस्या का कलनविधि प्राकृतिक संख्याओं के उपसमुच्चय के संकेतक क्रिया की गणना करना है।
उदाहरण
निर्णायक निर्णय समस्या का उत्कृष्ट उदाहरण अभाज्य संख्याओं का समुच्चय है। प्रभावी रूप से यह तय करना संभव है कि क्या दी गई प्राकृतिक संख्या हर संभव गैर-कारक के परीक्षण में प्रमुख है। यद्यपि प्रारंभिक परीक्षण के बहुत अधिक कुशल तरीके ज्ञात हैं, किसी भी प्रभावी विधि का अस्तित्व निर्णायकता स्थापित करने के लिए पर्याप्त है।
निर्णायकता
निर्णय समस्या निर्णायक या प्रभावी रूप से हल करने योग्य है यदि निवेश का समुच्चय (या प्राकृतिक संख्या) जिसके लिए उत्तर हाँ है, एक पुनरावर्ती समुच्चय है। समस्या आंशिक रूप से निर्णायक, अर्ध-निर्णायक, हल करने योग्य, या साबित करने योग्य है यदि निवेश का समुच्चय (या प्राकृतिक संख्या) जिसके लिए उत्तर हाँ है, पुनरावर्ती गणना योग्य समुच्चय है। समस्याएँ जो निर्णायक नहीं हैं वे अनिर्णीत हैं। उन लोगों के लिए कलनविधि बनाना संभव नहीं है, कुशल या अन्यथा, जो उन्हें हल कर सकता है।
हाल्टिंग की समस्या महत्वपूर्ण अनिर्णीत निर्णय समस्या है; अधिक उदाहरणों के लिए, अनिर्णीत समस्याओं की सूची देखें।
पूर्ण समस्याएं
निर्णय की समस्याओं को कई कमी के अनुसार आदेशित किया जाता है | कई समानेयता और व्यवहार्य कटौती से संबंधित जैसे कि बहुपद-समय में कमी है। निर्णय समस्या P को निर्णय समस्याओं के एक समुच्चय के लिए पूर्ण समस्या कहा जाता है यदि P, S का सदस्य है और S में प्रत्येक समस्या को P तक कम किया जा सकता है। पूर्ण निर्णय समस्याओं का उपयोग संगणनात्मक जटिलता सिद्धांत में निर्णय की जटिलता वर्गों की विशेषता के लिए किया जाता है। समस्या उदाहरण के लिए, बहुपद-समय समानेयताके अनुसार निर्णय समस्याओं के वर्ग एनपी (जटिलता) के लिए बूलियन संतुष्टि समस्या पूरी करी गई है।
समारोह की समस्याएं
निर्णय की समस्याएं कार्यात्मक समस्याओं से निकटता से संबंधित हैं, जिनके उत्तर सरल 'हां' या 'नहीं' से अधिक जटिल हो सकते हैं। संगत समारोह की समस्या में दो नंबर x और y दिए गए हैं, x को y से भाग देना क्या है? .
क्रिया समस्या में आंशिक क्रिया f होता है; अनौपचारिक समस्या उन निवेशों पर f के मानों की गणना करना है जिनके लिए इसे परिभाषित किया गया है।
प्रत्येक कार्य समस्या को निर्णय समस्या में बदला जा सकता है; निर्णय समस्या केवल संबंधित क्रिया का लेखाचित्र है। (क्रिया f का लेखाचित्र जोड़े (x, y) का समुच्चय है जैसे कि f(x) = y।) यदि यह निर्णय समस्या प्रभावी ढंग से हल करने योग्य थी तो क्रिया समस्या भी होगी। चूंकि, यह कमी संगणनात्मक जटिलता का सम्मान नहीं करती है। उदाहरण के लिए, किसी क्रिया के लेखाचित्र के लिए बहुपद समय में निर्णायक होना संभव है (जिस स्थिति में चल रहे समय की गणना जोड़ी (x,y) के क्रिया के रूप में की जाती है। जब क्रिया बहुपद समय में गणना योग्य नहीं होता है (जिसमें केस चलने के समय की गणना केवल x के कार्य के रूप में की जाती है)। फलन f(x) = 2x के पास यह गुण है।
निर्णय समस्या से जुड़े समुच्चय के सूचक क्रिया की गणना करने की प्रत्येक निर्णय समस्या को क्रिया समस्या में परिवर्तित किया जा सकता है। यदि यह कार्य गणना योग्य है तो संबंधित निर्णय समस्या निर्णायक है। चूंकि, यह कमी संगणनात्मक जटिलता में उपयोग की जाने वाली मानक कमी की तुलना में अधिक उदार है (जिसे कभी-कभी बहुपद-समय कमी कहा जाता है); उदाहरण के लिए, एनपी-पूर्ण समस्या और उसके सह-एनपी-पूर्ण पूरक (जटिलता) के विशिष्ट कार्यों की जटिलता बिल्कुल समान है, भले ही अंतर्निहित निर्णय समस्याओं को गणना के कुछ विशिष्ट प्रतिमा में समकक्ष नहीं माना जा सकता है।
अनुकूलन समस्याएं
निर्णय समस्याओं के विपरीत, जिसके लिए प्रत्येक निवेश के लिए केवल एक सही उत्तर होता है, अनुकूलन समस्याएँ किसी विशेष निवेश के सर्वोत्तम उत्तर खोजने से संबंधित होती हैं। कई अनुप्रयोगों में अनुकूलन समस्याएं स्वाभाविक रूप से उत्पन्न होती हैं, जैसे ट्रैवलिंग सेल्समैन की समस्या और रैखिक प्रोग्रामिंग के प्रश्न।
कार्य और अनुकूलन समस्याओं को निर्णय समस्याओं में बदलने के लिए मानक तकनीकें हैं। उदाहरण के लिए, ट्रैवलिंग सेल्समैन समस्या में, अनुकूलन समस्या न्यूनतम वजन के साथ परिक्रम तैयार करना है। संबंधित निर्णय समस्या है: प्रत्येक एन के लिए, यह तय करने के लिए कि लेखाचित्र में एन से कम वजन वाला कोई दौरा है या नहीं। निर्णय की समस्या का बार-बार उत्तर देकर, दौरे का न्यूनतम वजन खोजना संभव है।
क्योंकि निर्णय समस्याओं का सिद्धांत बहुत अच्छे प्रकार से विकसित है, जटिलता सिद्धांत में अनुसंधान ने विशेष रूप से निर्णय समस्याओं पर ध्यान केंद्रित किया है। अनुकूलन की समस्याएं अभी भी संगणनीयता सिद्धांत के साथ-साथ संचालन अनुसंधान जैसे क्षेत्रों में रुचि रखती हैं।
यह भी देखें
- सभी (जटिलता)
- संगणनात्मक समस्या
- निर्णायकता (तर्क) - यह तय करने की समस्या के लिए कि क्या कोई सूत्र तार्किक सिद्धांत का परिणाम है।
- खोज समस्या
- गिनती की समस्या (जटिलता)
- शब्द समस्या (गणित)
संदर्भ
- 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.
- ↑ "CS254: Computational Complexity: Lecture 2" (PDF). Archived (PDF) from the original on 2015-10-10.
