कम्प्यूटेशनल समस्या

सैद्धांतिक कंप्यूटर विज्ञान में, कम्प्यूटेशनल समस्या एक समस्या है जिसे कलन विधि द्वारा हल किया जा सकता है। उदाहरण के लिए, फैक्टरिंग की समस्या

"एक धनात्मक पूर्णांक n दिया हुआ है, n का एक गैर-तुच्छ अभाज्य गुणनखंड ज्ञात कीजिए।"

कम्प्यूटेशनल समस्या है। एक कम्प्यूटेशनल समस्या को उदाहरण या स्तिथि के एक सम्मुच्चय (गणित) के रूप में देखा जा सकता है, साथ में हर उदाहरण/स्तिथि के लिए संभवतः खाली, समाधान का सम्मुच्चय। उदाहरण के लिए, फैक्टरिंग समस्या में, उदाहरण पूर्णांक n हैं, और समाधान अभाज्य संख्याएँ p हैं जो n के गैर-तुच्छ अभाज्य गुणनखंड हैं।

कम्प्यूटेशनल समस्याएं सैद्धांतिक कंप्यूटर विज्ञान में अध्ययन की मुख्य वस्तुओं में से एक हैं। कम्प्यूटेशनल जटिलता सिद्धांत का क्षेत्र संसाधनों की मात्रा (कम्प्यूटेशनल जटिलता) निर्धारित करने का प्रयास करता है, किसी समस्या को हल करने के लिए आवश्यकता होगी और समझाएगा कि क्यों कुछ समस्याएं कम्प्यूटेशनल जटिलता सिद्धांत या अनिर्णीत समस्या हैं। कम्प्यूटेशनल समस्याएं जटिलता वर्ग से संबंधित हैं जो स्थूलतः संसाधनों को परिभाषित करती हैं (जैसे समय, स्थान/स्मृति, ऊर्जा, सर्किट की गहराई) उन्हें विभिन्न अमूर्त मशीनों के साथ गणना (हल) करने में लगती है। उदाहरण के लिए, जटिलता वर्ग P (जटिलता) (पारम्परिक मशीनों के लिए बहुपद समय), और परिमाण मशीनों के लिए BQP है।

उदाहरण और समाधान दोनों को द्विचर श्रृंखला (कंप्यूटर विज्ञान) द्वारा दर्शाया जाता है, अर्थात् {0, 1} ^{तत्व के उदाहरण के लिए, प्राकृतिक संख्याओं को सामान्यतः द्विचर संख्या का उपयोग करके द्विचर श्रृंखला के रूप में दर्शाया जाता है। यह महत्वपूर्ण है क्योंकि जटिलता को इनपुट प्रतिनिधित्व की लंबाई के एक फलन के रूप में व्यक्त किया गया है।}

प्रकार

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

निर्णय समस्या एक कम्प्यूटेशनल समस्या है जहां हर उदाहरण का उत्तर हां या नहीं है। निर्णय समस्या का एक उदाहरण प्रारंभिक परीक्षण है:

एक सकारात्मक पूर्णांक n दिया गया है, निर्धारित करें कि क्या n अभाज्य है।

एक निर्णय समस्या को सामान्यतः उन सभी उदाहरणों के सम्मुच्चय के रूप में दर्शाया जाता है जिनके लिए उत्तर हां है। उदाहरण के लिए, प्राथमिक परीक्षण को अनंत सम्मुच्चय के रूप में दर्शाया जा सकता है

L = {2, 3, 5, 7, 11, ...}

खोज समस्या

एक खोज समस्या में, उत्तर स्वेच्छाचारी श्रंखला हो सकता है। उदाहरण के लिए, फैक्टरिंग एक खोज समस्या है जहां उदाहरण सकारात्मक पूर्णांकों के (श्रृंखला प्रतिनिधित्व) हैं और समाधान प्राइम्स के संग्रह (श्रृंखला प्रतिनिधित्व) हैं।

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

R = {(4, 2), (6, 2), (6, 3), (8, 2), (9, 3), (10, 2), (10, 5)...}

जिसमें संख्याओं के सभी युग्म (n, p) सम्मिलित हैं, जहाँ p, n का एक गैर-तुच्छ अभाज्य गुणक है।

गिनती की समस्या

एक गिनती समस्या (जटिलता) किसी दी गई खोज समस्या के समाधान की संख्या के लिए पूछती है। उदाहरण के लिए, फैक्टरिंग से जुड़ी एक गिनती की समस्या है

एक सकारात्मक पूर्णांक n दिया गया है, n के गैर-तुच्छ अभाज्य कारकों की संख्या की गणना करें।

गिनती की समस्या को {0, 1} के फलन f द्वारा अऋणात्मक पूर्णांकों के लिए प्रदर्शित किया जा सकता है। एक खोज संबंध R के लिए, R से संबंधित गणना समस्या फलन है

f_R(x) = |{y: R(x, y) }|

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

एक अनुकूलन समस्या खोज समस्या के सभी संभावित समाधानों के सम्मुच्चय के बीच एक सर्वोत्तम संभव समाधान खोजने के लिए कहती है। एक उदाहरण अधिकतम स्वतंत्र समुच्चय समस्या है:

एक लेखाचित्र G दिया गया है, अधिकतम आकार के G का एक स्वतंत्र सम्मुच्चय खोजें।

अनुकूलन समस्याओं को उनके उद्देश्य फलन और उनकी बाधाओं से दर्शाया जाता है।

कार्य समस्या

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

शहरों की सूची और शहरों की प्रत्येक जोड़ी के बीच की दूरी को देखते हुए, सबसे छोटा संभव मार्ग खोजें जो प्रत्येक शहर में ठीक एक बार जाता है और मूल शहर में लौटता है।

संयोजी अनुकूलन में यह एक NP-कठोर समस्या है, संचालन अनुसंधान और सैद्धांतिक कंप्यूटर विज्ञान में महत्वपूर्ण है।

वचन समस्या

Main article: वचन समस्या

कम्प्यूटेशनल जटिलता सिद्धांत में, सामान्यतः यह माना जाता है कि {0, 1} में कोई श्रृंखला^* विचाराधीन कम्प्यूटेशनल समस्या का एक उदाहरण प्रस्तुत करता है। हालांकि, कभी-कभी सभी श्रृंखला {0, 1} मान्य उदाहरणों का प्रतिनिधित्व नहीं^* करते हैं, और एक {0, 1} का उचित उपसमुच्चय मान्य उदाहरणों के सम्मुच्चय के रूप में निर्दिष्ट करता है। इस प्रकार की कम्प्यूटेशनल समस्याओं को वचन समस्या कहा जाता है।

निम्नलिखित एक (निर्णय) वचन समस्या का एक उदाहरण है:

एक लेखाचित्र G दिया गया है, यह निर्धारित करें कि G में प्रत्येक स्वतंत्र सम्मुच्चय (लेखाचित्र सिद्धांत) का आकार अधिकतम 5 है, या G के आकार का एक स्वतंत्र सम्मुच्चय कम से कम 10 है।

यहां, मान्य उदाहरण वे आलेख हैं जिनका अधिकतम स्वतंत्र सम्मुच्चय आकार या तो अधिकतम 5 या कम से कम 10 है।

निर्णय वादा समस्याओं को सामान्यतः {0, 1}* के असंयुक्त उपसमुच्चय (L_yes, L_no) के जोड़े के रूप में दर्शाया जाता है। L_yes ∪ L_no. में वैध उदाहरण हैं। L_yesऔर L_no उन उदाहरणों का प्रतिनिधित्व करते हैं जिनका उत्तर क्रमशः हाँ और नहीं है।

कलन विधि के विश्लेषण के कई क्षेत्रों में वचन की समस्याएं एक महत्वपूर्ण भूमिका निभाती हैं, जिसमें सन्निकटन की कठोरता, संपत्ति परीक्षण और पारस्परिक प्रमाण प्रणाली सम्मिलित हैं।

यह भी देखें

• पार्श्व कंप्यूटिंग, कम्प्यूटेशनल रूप से समस्याओं को हल करने के लिए वैकल्पिक दृष्टिकोण
• गणना का प्रतिरूप
• ट्रांसकंप्यूटेशनल समस्या

संदर्भ

• Even, Shimon; Selman, Alan L.; Yacobi, Yacov (1984), "The complexity of promise problems with applications to public-key cryptography", Information and Control, 61 (2): 159–173, doi:10.1016/S0019-9958(84)80056-X.
• Goldreich, Oded (2008), Computational Complexity: A Conceptual Perspective, Cambridge University Press, ISBN 978-0-521-88473-0.
• Goldreich, Oded; Wigderson, Avi (2008), "IV.20 Computational Complexity", in Gowers, Timothy; Barrow-Green, June; Leader, Imre (eds.), The Princeton Companion to Mathematics, Princeton University Press, pp. 575–604, ISBN 978-0-691-11880-2.