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