एसएटी (बूलियन सन्तुष्टि) समस्या NP-पूर्ण समस्या हुन सक्छ कि भन्ने प्रश्न कम्प्युटेसनल जटिलता सिद्धान्तमा आधारभूत हो। यसलाई सम्बोधन गर्न, NP-पूर्णताको परिभाषा र गुणहरू विचार गर्न र NP-पूर्ण समस्याको रूपमा SAT को वर्गीकरण गर्ने ऐतिहासिक र सैद्धान्तिक सन्दर्भलाई जाँच्न आवश्यक छ।
परिभाषा र सन्दर्भ
SAT समस्या: SAT समस्याले दिइएको बुलियन सूत्रलाई सत्य बनाउने चरहरूमा सत्य मानहरूको असाइनमेन्ट अवस्थित छ कि छैन भनेर निर्धारण गर्ने समावेश छ। एक बुलियन सूत्र सामान्यतया संयोजक सामान्य रूप (CNF) मा व्यक्त गरिन्छ, जहाँ सूत्र खण्डहरूको संयोजन हो, र प्रत्येक खण्ड शाब्दिकहरूको विच्छेदन हो। उदाहरण को लागी, एक सूत्र जस्तो देखिन सक्छ:
NP (Nondeterministic बहुपद समय): एक निर्णय समस्या NP मा छ यदि एक निश्चित समाधान एक निश्चित ट्युरिङ मेसिन द्वारा बहुपद समयमा सही वा गलत रूपमा प्रमाणित गर्न सकिन्छ। अनिवार्य रूपमा, यदि तपाइँसँग उम्मेद्वार समाधान छ भने, तपाइँ यसको वैधता कुशलतापूर्वक जाँच गर्न सक्नुहुन्छ।
NP- पूरा: समस्या NP-पूर्ण हुन्छ यदि यसले दुई सर्तहरू पूरा गर्छ भने:
1. यो NP मा छ।
2. NP मा हरेक समस्या बहुपद समयमा यसलाई कम गर्न सकिन्छ।
NP-पूर्णताको अवधारणा स्टीफन कुकले आफ्नो सेमिनल 1971 पेपर "द कम्प्लेक्सिटी अफ थ्योरेम-प्रोभिङ प्रोसिजर" मा प्रस्तुत गरेका थिए जहाँ उनले SAT समस्या पहिलो ज्ञात NP-पूर्ण समस्या हो भनी प्रदर्शन गरे। यो नतिजा अब कुकको प्रमेयको रूपमा चिनिन्छ।
कुकको प्रमेय र यसको प्रभावहरू
किन SAT NP-पूर्ण छ बुझ्नको लागि, हामीले दुई मुख्य बुँदाहरू स्थापित गर्न आवश्यक छ:
1. SAT NP मा छ।
2. NP मा हरेक समस्यालाई बहुपदीय समयमा SAT मा घटाउन सकिन्छ।
SAT NPमा हुनुहुन्छ
SAT NP मा छ भनेर प्रमाणित गर्न, बुलियन सूत्र र यसको चरहरूमा सत्य मानहरूको प्रस्तावित असाइनमेन्टलाई विचार गर्नुहोस्, हामी सूत्रले बहुपदीय समयमा सत्य मूल्याङ्कन गर्छ कि गर्दैन भनेर जाँच गर्न सक्छौं। यसमा प्रत्येक खण्डमा कम्तिमा एक शाब्दिक सत्य छ कि भनेर हेर्नको लागि सूत्रमा प्रत्येक खण्डको मूल्याङ्कन समावेश गर्दछ। बुलियन सूत्रको मूल्याङ्कन गर्नु एउटा सीधा प्रक्रिया हो जसमा सीमित संख्यामा तार्किक कार्यहरू समावेश हुन्छन्, यसलाई प्रभावकारी रूपमा गर्न सकिन्छ। यसरी, SAT NP मा छ किनभने हामी बहुपद समयमा समाधान प्रमाणित गर्न सक्छौं।
बहुपद-समय कटौती
SAT NP-पूर्ण छ भनेर प्रमाणित गर्ने थप चुनौतीपूर्ण भागले NP मा भएका हरेक समस्यालाई बहुपदीय समयमा SAT मा घटाउन सकिन्छ भनेर देखाउँदैछ। यसमा NP मा कुनै पनि समस्याको लागि, त्यहाँ एक बहुपद-समय कम्प्युटेबल प्रकार्य अवस्थित छ जसले समस्याको उदाहरणहरूलाई SAT को उदाहरणहरूमा रूपान्तरण गर्दछ कि मूल समस्याको समाधान हुन्छ यदि रूपान्तरित SAT उदाहरण सन्तोषजनक छ भने मात्र।
यो चित्रण गर्न, एक सामान्य समस्या विचार गर्नुहोस् NP मा। परिभाषा अनुसार, त्यहाँ एक nondeterministic बहुपद-समय ट्युरिङ मेसिन अवस्थित छ
जसले निर्णय गर्छ
। मेसिन
दिइएको प्रमाणपत्र (समाधान) मान्य छ कि छैन भनेर जाँच गर्न सक्ने बहुपद-समय प्रमाणिकरण प्रक्रिया छ। हामी को अपरेशन एन्कोड गर्न सक्छौं
इनपुटमा
बुलियन सूत्रको रूपमा जस्तै कि सूत्र सन्तोषजनक छ यदि र मात्र
स्वीकार्छ
.
एन्कोडिङले निम्न चरणहरू समावेश गर्दछ:
1. कन्फिगरेसन एन्कोडिङ: को कन्फिगरेसनहरू (राज्यहरू, टेप सामग्रीहरू, र हेड स्थितिहरू) इन्कोड गर्नुहोस् बुलियन चरको रूपमा। प्रत्येक कन्फिगरेसन बिट्स को एक अनुक्रम द्वारा प्रतिनिधित्व गर्न सकिन्छ।
2. ट्रान्जिसन एन्कोडिङ: को ट्रान्जिसन प्रकार्य इन्कोड गर्नुहोस् बुलियन अवरोधहरूको सेटको रूपमा। यी अवरोधहरूले कन्फिगरेसनहरू बीचको वैध संक्रमणहरू क्याप्चर गरिएको छ भनी सुनिश्चित गर्दछ।
3. प्रारम्भिक र स्वीकार्य राज्यहरू: प्रारम्भिक कन्फिगरेसन (जब मेसिन सुरु हुन्छ) र स्वीकार गर्ने कन्फिगरेसन (जब मेसिन रोकिन्छ र स्वीकार गर्दछ) बुलियन अवरोधहरूको रूपमा इन्कोड गर्नुहोस्।
बूलियन सूत्र निर्माण गरेर जसले व्यवहारलाई क्याप्चर गर्दछ , हामी SAT को एक उदाहरण सिर्जना गर्छौं जुन सन्तोषजनक छ यदि मान्य ट्रान्जिसनहरूको अनुक्रम हो भने मात्र स्वीकार्य राज्यमा जान्छ। यो कमी इनपुटको आकारको सापेक्ष बहुपद समयमा प्रदर्शन गर्न सकिन्छ
.
उदाहरण: 3-SAT बाट SAT मा कटौती
बहुपद-समय घटाउने अवधारणालाई थप स्पष्ट गर्न, 3-SAT लाई SAT मा घटाउने विशिष्ट मामलालाई विचार गर्नुहोस्। 3-SAT समस्या SAT को एक विशेष केस हो जहाँ प्रत्येक खण्डमा ठीक तीन अक्षरहरू छन्। 3-SAT लाई SAT मा घटाउनको लागि, हामी सजिलै देख्न सक्छौं कि कुनै पनि 3-SAT उदाहरण पहिले नै SAT द्वारा आवश्यक फारममा छ (अर्थात, CNF सूत्र)। त्यसकारण, कटौती तुच्छ छ र रैखिक समयमा गर्न सकिन्छ, जुन बहुपद-समय कटौती हो।
SAT को निहितार्थ NP-पूर्ण हुनु
NP-complete को रूपमा SAT को वर्गीकरणले कम्प्युटेशनल जटिलता सिद्धान्त र व्यावहारिक समस्या समाधानका लागि गहिरो प्रभाव पार्छ। SAT NP-पूर्ण भएकोले, NP मा कुनै पनि समस्यालाई SAT उदाहरणमा अनुवाद गर्न सकिन्छ। यो सार्वभौमिकता भनेको SAT ले अन्य समस्याहरूको जटिलताको लागि बेन्चमार्कको रूपमा कार्य गर्दछ। यदि हामीले SAT लाई समाधान गर्न बहुपद-समय एल्गोरिथ्म फेला पार्न सक्छौं भने, हामी सबै NP समस्याहरू बहुपद समयमा समाधान गर्न सक्छौं, यसको अर्थ .
यसको विपरित, यदि हामीले SAT को लागि कुनै बहुपद-समय एल्गोरिथ्म अवस्थित छैन भनेर प्रमाणित गर्छ भने, यसले संकेत गर्दछ कि । व्यापक अनुसन्धानको बाबजुद पनि प्रश्न उठेको छ
कम्प्युटर विज्ञानमा सबैभन्दा महत्त्वपूर्ण खुला समस्याहरू मध्ये एक रहन्छ।
व्यावहारिक अनुप्रयोगहरू
अभ्यासमा, सफ्टवेयर प्रमाणिकरण, कृत्रिम बुद्धिमत्ता, र क्रिप्टोग्राफी सहित विभिन्न डोमेनहरूमा SAT समाधानहरू व्यापक रूपमा प्रयोग गरिन्छ। आधुनिक SAT समाधानकर्ताहरूले SAT को सैद्धान्तिक NP-पूर्णताको बावजुद, ठूला र जटिल उदाहरणहरूलाई कुशलतापूर्वक ह्यान्डल गर्न परिष्कृत एल्गोरिदम र हेरिस्टिक्सको लाभ उठाउँछन्। यी समाधानकर्ताहरूले वास्तविक-विश्व समस्याहरू समाधान गर्न सम्भव बनाएका छन् जुन पहिले असम्भव थियो।
निष्कर्ष
कुकको प्रमेय द्वारा स्थापित SAT समस्या वास्तवमा NP-पूर्ण समस्या हो। यो वर्गीकरण यस तथ्यमा आधारित छ कि SAT NP मा छ र NP मा हरेक समस्यालाई बहुपद समयमा SAT मा घटाउन सकिन्छ। एसएटी NP-पूर्ण हुनुको प्रभावहरू दूरगामी छन्, दुबै सैद्धान्तिक अनुसन्धान र कम्प्युटर विज्ञानमा व्यावहारिक अनुप्रयोगहरूलाई प्रभाव पार्छ।
अन्य भर्खरका प्रश्न र उत्तरहरू सम्बन्धमा जटिलता:
- के PSPACE वर्ग EXPSPACE वर्गको बराबर छैन?
- के P जटिलता वर्ग PSPACE वर्गको उपसमूह हो?
- के हामी एक निश्चित TM मा कुनै पनि NP पूर्ण समस्याको लागि एक कुशल बहुपद समाधान खोजेर Np र P वर्ग समान छन् भनेर प्रमाणित गर्न सक्छौं?
- के NP वर्ग EXPTIME कक्षा बराबर हुन सक्छ?
- के PSPACE मा समस्याहरू छन् जसको लागि कुनै ज्ञात NP एल्गोरिथ्म छैन?
- के NP जटिलता वर्गमा समस्या हुन सक्छ यदि त्यहाँ एक गैर-निर्धारित ट्युरिङ मेसिन छ जसले यसलाई बहुपद समयमा समाधान गर्नेछ।
- NP बहुपदीय समय प्रमाणिकरण भएका भाषाहरूको वर्ग हो
- के P र NP वास्तवमा एउटै जटिलता वर्ग हो?
- के प्रत्येक सन्दर्भ मुक्त भाषा P जटिलता वर्गमा छ?
- के त्यहाँ बहुपद-समय प्रमाणिकरणहरूको साथ निर्णय समस्याहरूको वर्गको रूपमा NP को परिभाषा र वर्ग P मा पनि बहुपद-समय प्रमाणिकरणहरू छन् भन्ने तथ्य बीचको विरोधाभास छ?
जटिलतामा थप प्रश्न र उत्तरहरू हेर्नुहोस्