Berman–Hartmanis conjecture
संरचनात्मक जटिलता सिद्धांत में, बर्मन-हार्टमैनिस अनुमान एक अनसुलझा अनुमान है जिसका नाम लियोनार्ड सी. बर्मन और ज्यूरिस हार्टमैनिस के नाम पर रखा गया है जिसमें कहा गया है कि सभी एन. पी.-पूर्ण भाषाएँ एक जैसी दिखती हैं, इस अर्थ में कि वे बहुपद समय समरूपता द्वारा एक दूसरे से संबंधित हो सकती हैं। कथन औपचारिक भाषाओं L1 और L2 के बीच एक समरूपता L1 की वर्णमाला में स्ट्रिंग्स से लेकर L2 की वर्णमाला में स्ट्रिंग्स तक एक बाइजेक्टिव मैप f है, इस गुण के साथ कि एक स्ट्रिंग x L1 से संबंधित है यदि और केवल अगर f (x) L2 से संबंधित है। यह एक बहुपद समय समरूपता (या संक्षेप में पी-समरूपता) है यदि एफ और इसके व्युत्क्रम फलन दोनों की गणना उनके तर्कों की लंबाई में समय बहुपद की मात्रा में की जा सकती है। यह देखा गया कि उस समय एन. पी.-पूर्ण होने के लिए जानी जाने वाली सभी भाषाएँ पी-समरूपी थीं। अधिक दृढ़ता से, उन्होंने देखा कि सभी तत्कालीन ज्ञात एन. पी.-पूर्ण भाषाएँ पैडेबल थीं, और उन्होंने साबित किया (माइल आइसोमोर्फिज्म प्रमेय के अनुरूप) कि पैडेबल एन. पी.-पूर्ण भाषाओं के सभी जोड़े पी-आइसोमोर्फिक हैं। यदि बहुपद समय व्युत्क्रम के साथ एक बहुपद समय फलन f (x, y) है और इस गुण के साथ कि सभी x और y के लिए, x L से संबंधित है यदि और केवल यदि f (x, y) L से संबंधित हैः अर्थात, इनपुट x को अप्रासंगिक जानकारी y के साथ, एक व्युत्क्रमणीय तरीके से, भाषा में अपनी सदस्यता को बदले बिना पैड करना संभव है। इन परिणामों के आधार पर, बर्मन और हार्टमैनिस ने अनुमान लगाया कि सभी एनपी-पूर्ण भाषाएँ पी-आइसोमोर्फिक हैं। चूँकि पी-समरूपता पैडेबिलिटी को संरक्षित करती है, और पैडेबल एनपी-पूर्ण भाषाएँ मौजूद हैं, बर्मन-हार्टमैनिस अनुमान को बताने का एक समकक्ष तरीका यह है कि सभी एनपी-पूर्ण भाषाएँ पैडेबल हैं। बहुपद समय समरूपता एक समतुल्यता संबंध है, और इसका उपयोग औपचारिक भाषाओं को समतुल्यता वर्गों में विभाजित करने के लिए किया जा सकता है, इसलिए बर्मन-हार्टमैनिस अनुमान को बताने का एक और तरीका यह है कि एन. पी.-पूर्ण भाषाएं इस संबंध के लिए एक एकल समतुल्यता वर्ग बनाती हैं। प्रभाव यदि बर्मन-हार्टमैनिस का अनुमान सही है, तो एक तत्काल परिणाम विरल एन. पी.-पूर्ण भाषाओं का अस्तित्व नहीं होना होगा, अर्थात् ऐसी भाषाएँ जिनमें लंबाई एन के हाँ-उदाहरणों की संख्या केवल एन के फलन के रूप में बहुपद रूप से बढ़ती है। ज्ञात एन. पी.-पूर्ण भाषाओं में कई हाँ-उदाहरण हैं जो तेजी से बढ़ते हैं, और यदि एल तेजी से कई हाँ-उदाहरणों वाली भाषा है, तो यह एक विरल भाषा के लिए पी-समरूप नहीं हो सकती है, क्योंकि मानचित्रण को एक-से-एक होने के लिए इसके हाँ-उदाहरणों को उन तारों के लिए मैप करना होगा जो बहुपद रूप से लंबे से अधिक हैं। बदले में विरल एन. पी.-पूर्ण भाषाओं की अनुपस्थिति का तात्पर्य है कि पी ≤ एन. पी., क्योंकि यदि पी = एन. पी. है तो पी. में प्रत्येक गैर-तुच्छ भाषा (कुछ विरल भाषाओं सहित, जैसे कि द्विआधारी तारों की भाषा, जिनके सभी बिट्स शून्य हैं) एन. पी.-पूर्ण होगी। 1982 में, स्टीव महानी ने अपना प्रमाण प्रकाशित किया कि विरल एन. पी.-पूर्ण भाषाओं की अनुपस्थिति (कई-एक कटौती का उपयोग करके मानक तरीके से परिभाषित एन. पी.-पूर्णता के साथ) वास्तव में इस कथन के बराबर है कि पी ष्णांक एन. पी.; यह महानी की प्रमेय है। यहां तक कि ट्यूरिंग कटौती का उपयोग करके एन. पी.-पूर्णता की एक आरामदायक परिभाषा के लिए, एक विरल एन. पी.-पूर्ण भाषा का अस्तित्व बहुपद पदानुक्रम के अप्रत्याशित पतन का संकेत देगा। अनुमान की ओर साक्ष्य के रूप में, यह दिखाया गया है कि एक सीमित प्रकार की कमी के साथ एक समान अनुमान सच हैः प्रत्येक दो भाषाएँ जो AC0 कई-एक कटौती के तहत NP के लिए पूर्ण हैं, उनमें AC0 समरूपता होती है। यह दर्शाता है कि, यदि एक तरफा फलन मौजूद हैं जिन्हें सभी निवेशों पर बहुपद समय में उल्टा नहीं किया जा सकता है, लेकिन यदि ऐसे प्रत्येक फलन में निवेशों का एक छोटा लेकिन घना उपसमुच्चय है जिस पर इसे पी/पॉली में उल्टा किया जा सकता है (जैसा कि इस प्रकार के ज्ञात कार्यों के लिए सच है) तो प्रत्येक दो एनपी-पूर्ण भाषाओं में पी/पॉली समरूपता होती है। और एक ओरेकल मशीन मॉडल पाया जिसमें समरूपता अनुमान का अनुरूप सच है। अनुमान के खिलाफ साक्ष्य और द्वारा प्रदान किया गया था। जोसेफ और यंग ने एन. पी.-पूर्ण समस्याओं का एक वर्ग, के-रचनात्मक समुच्चय पेश किया, जिसके लिए मानक एन. पी.-पूर्ण समस्याओं के लिए कोई पी-समरूपता ज्ञात नहीं है। कर्ट्ज़ एट अल। यह दर्शाता है कि ऑरेकल मशीन मॉडल में यादृच्छिक ऑरेकल तक पहुंच दी जाती है, तो अनुमान का अनुरूप सच नहीं हैः यदि ए एक यादृच्छिक ऑरेकल है, तो एन. पी. ए. के लिए पूर्ण सभी सेटों में पी. ए. में समरूपता नहीं होती है। यादृच्छिक ऑरेकल का उपयोग आमतौर पर क्रिप्टोग्राफी के सिद्धांत में क्रिप्टोग्राफिक हैश कार्यों को मॉडल करने के लिए किया जाता है जो यादृच्छिक से कम्प्यूटेशनल रूप से अप्रभेद्य होते हैं, और कर्ट्ज़ एट अल का निर्माण। ओरेकल के स्थान पर इस तरह के कार्य के साथ किया जा सकता है। इस कारण से, कई जटिलता सिद्धांतकारों द्वारा बर्मन-हार्टमैनिस समरूपता अनुमान को गलत माना जाता है। संरचनात्मक जटिलता सिद्धांत कंप्यूटर विज्ञान में अनसुलझी समस्याओं का अनुमान लगाता है गणित में अनसुलझी समस्याएं