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

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

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

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

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

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

प्रकार

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

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

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

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

एल = {2, 3, 5, 7, 11, ...}

खोज समस्या

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

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

आर = {(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 से संबंधित गणना समस्या फलन है

एफ_R(एक्स) = |{वाई: आर(एक्स, वाई)}|।

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

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

एक ग्राफ जी दिया गया है, अधिकतम आकार के जी का एक स्वतंत्र सेट खोजें।

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

कार्य समस्या

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

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

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

वादा समस्या

Main article: Promise problem

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

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

एक ग्राफ जी दिया गया है, यह निर्धारित करें कि जी में प्रत्येक स्वतंत्र सेट (ग्राफ सिद्धांत) का आकार अधिकतम 5 है, या जी के आकार का एक स्वतंत्र सेट कम से कम 10 है।

यहां, मान्य उदाहरण वे ग्राफ़ हैं जिनका अधिकतम स्वतंत्र सेट आकार या तो अधिकतम 5 या कम से कम 10 है।

निर्णय वादा समस्याओं को आम तौर पर अलग-अलग उपसमुच्चय के जोड़े के रूप में दर्शाया जाता है (एल_yes, एल_no) {0, 1} का^{*</सुप>. वैध उदाहरण एल में हैं_yes ∪ एल_no. एल_yes और मैं_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.