न्यूनीकरण और अघुलनशीलता की कोटियाँ

न्यूनीकरण समस्याओं की कठिनाई की तुलना एक को दूसरे में रूपांतरित करके करता है, और समान कठिनाई वाली समस्याओं को समूहित करने से अघुलनशीलता की कोटियाँ उत्पन्न होती हैं जो संगणनीय से परे की दुनिया को संरचित करती हैं।

Definition

एक समस्या दूसरी समस्या तक कम हो जाती है जब दूसरी समस्या के लिए एक सॉल्वर तक पहुंच के साथ एक एल्गोरिथम पहली समस्या को हल कर सकता है; जो समस्याएं एक-दूसरे तक कम हो जाती हैं वे अघुलनशीलता की एक डिग्री साझा करती हैं, और ये डिग्री सापेक्ष एल्गोरिथम कठिनाई को मापने वाला एक क्रम बनाती हैं।

Scope

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

Core questions

• हम कैसे कह सकते हैं कि एक अघुलनशील समस्या दूसरी से कठिन है?
• न्यूनीकरण का उपयोग अनिर्णयता को सिद्ध करने और समस्याओं को व्यवस्थित करने दोनों के लिए कैसे किया जाता है?
• ट्यूरिंग जंप क्या उत्पन्न करता है, और यह हमेशा कड़ाई से कठिन क्यों होता है?
• क्या निर्णय योग्य और हॉल्टिंग समस्या के बीच कड़ाई से कोई समस्याएँ हैं?

Key theories

न्यूनीकरण और ट्यूरिंग जंप

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

मध्यवर्ती डिग्री का अस्तित्व

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

Clinical relevance

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

History

ट्यूरिंग ने 1939 में ओरेकल मशीनों की शुरुआत की, और पोस्ट ने 1944 में अघुलनशीलता की डिग्री के अध्ययन को तैयार किया और यह समस्या उठाई कि क्या मध्यवर्ती संगणनीय गणनीय डिग्री मौजूद हैं। फ्रीडबर्ग और मुचनिक ने 1956-1957 में प्राथमिकता विधि का आविष्कार करके इसे स्वतंत्र रूप से हल किया, जो विषय की एक केंद्रीय तकनीक बन गई।

Key figures

• Emil Post
• Alan Turing
• Richard Friedberg
• Albert Muchnik

Seminal works

• soare2016
• rogers1987

Frequently asked questions

सहज रूप से न्यूनीकरण क्या है?

यह एक समस्या को दूसरी समस्या के सॉल्वर का उपयोग करके हल करने का एक तरीका है। यदि आप समस्या A के किसी भी उदाहरण को समस्या B के उदाहरण में अनुवाद कर सकते हैं ताकि उत्तर मेल खाते हों, तो B कम से कम A जितना कठिन है, और B का समाधान A का समाधान प्रदान करता है।

क्या हॉल्टिंग समस्या से कठिन समस्याएँ हैं?

हाँ, अनगिनत। हॉल्टिंग समस्या पर ट्यूरिंग जंप लागू करने से कड़ाई से कठिन समस्या उत्पन्न होती है, और ऑपरेशन को दोहराने से एक अंतहीन पदानुक्रम बनता है, इसलिए अघुलनशीलता एक ही स्तर के बजाय असीमित डिग्री में आती है।