क्या हाइपरबोलिक स्पेस के सेलुलर ऑटोमेटा में पी = एनपी है?
मैंने इस पुस्तक में कुछ साल पहले पढ़ा था कि हाइपरबोलिक प्लेन में सेलुलर ऑटोमेटा के स्थान पर एनपी की समस्याएं काफी हद तक सुगम हैं । इसका क्या मतलब है? क्या P = NPइन पुस्तकों / पत्रों के अनुसार?
कागज के कुछ अंश:
यह सर्वविदित है कि यदि हमारे पास "मुफ्त" में बाइनरी पेड़ हैं, तो बहुपद समय में एनपी-समस्याओं को हल करना संभव है, देखें [14, 5]। हालांकि, पेंटाग्रिड में बाइनरी ट्री एल्गोरिदम को लागू करना तत्काल नहीं है, और इस खंड का लक्ष्य यह इंगित करना है कि कोई कैसे आगे बढ़ सकता है।
मेरी समझ से, पी = एनपी समस्या जटिल समस्याओं को हल करने के लिए बहुपद-काल एल्गोरिदम की तलाश कर रही है। किताबों और पत्रों के माध्यम से मेरी सरसरी निगाह से यह पता चलता है कि उन्होंने समस्या हल कर दी है। मैं क्या खो रहा हूँ?
यहाँ एक और पेपर है, जिसका शीर्षक है इन द कर्व्ड स्पेसेस, वी कैन सॉल्व एनपी-हार्ड प्रॉब्लम्स इन पोलिनोमियल टाइम: टुवर्ड्स माटियासेविच ड्रीम ।
जवाब
पी बनाम एनपी समस्या ट्यूरिंग मशीनों के बारे में एक प्रश्न है $T$, क्योंकि इन सैद्धांतिक मशीनों के संदर्भ में जटिलता कक्षाएं P और NP परिभाषित हैं। चलो इन कक्षाओं को बुलाओ$P_T$ तथा $NP_T$अब से। कागज एक नई सैद्धांतिक संगणना मशीन का परिचय देता है$H$ जिसमें संबद्ध कक्षाएं हैं $P_H$ (हाइपरबोलिक सेलुलर ऑटोमेटन पर बहुपद समय में चलता है) और $NP_H$ (हाइपरबोलिक सेलुलर ऑटोमेटन पर गैर-नियतात्मक बहुपद समय में चलता है)।
इस पत्र में पहला कदम एक प्रमाण है कि 3SAT समस्या, एक प्रसिद्ध $NP_T$- अपूर्ण समस्या, इस मशीन पर बहुपद समय में हल किया जा सकता है, अर्थात यह समस्या निहित है $P_H$। इसके बाद, वे दिखाते हैं कि किसी भी बहुपद समय में कमी ट्यूरिंग मशीन पर बहुरंगी समय में उनके हाइपरबोलिक ऑटोमैटन पर की जा सकती है। चूंकि 3SAT है$NP_T$- अपूर्ण, कोई भी $NP_T$ उदाहरण को बहुपद समय में 3SAT उदाहरण पर घटाया जा सकता है (पर) $T$ परिभाषा से, इसलिए भी $H$उनके लेम्मा द्वारा) और फिर पॉली-टाइम में 3 एसएटी को हल करके, दोनों को हाइपरबोलिक ऑटोमेटन पर हल किया जा सकता है। दूसरे शब्दों में, इस पत्र का मुख्य परिणाम (प्रमेय 1) के रूप में लिखा जा सकता है$NP_T \subseteq P_H$हमारे अंकन में। यह पी बनाम एनपी समस्या का समाधान नहीं देता है, क्योंकि इसे कक्षाओं से संबंधित होना चाहिए$NP_T$ तथा $P_T$।
ध्यान दें कि लेखकों ने धारा 4.2 में पी बनाम एनपी समस्या पर कुछ टिप्पणियां शामिल हैं, जहां उनका दावा है कि उनका परिणाम पी के लिए सबूत है$\neq$एनपी (!):
एक तीसरी दिशा में साधारण सेटिंग्स में पी = एनपी प्रश्न पर नए प्रकाश शेड शामिल हैं। चूँकि हाइपरबोलिक स्पेस में गुण होते हैं जो यूक्लिडियन स्पेस के गुणों से बहुत अलग होते हैं, विशेष रूप से, इसमें कई और दिशाएँ होती हैं, तो यह संकेत देने के लिए अनुकूल नहीं होगा कि पी।$\neq$यूक्लिडियन स्थितियों में एनपी? ऐसा लगता है कि पिछले दस वर्षों से जटिलता के क्षेत्र में काम करने वाले लोगों को पी में अधिक विश्वास करने के लिए प्रेरित करता है$\neq$एनपी। जाहिर है, वर्तमान परिणाम भी उस प्रवृत्ति का है।