P बनाम NP और जीरो-नॉलेज प्रूफ्स में इसका अनुप्रयोग

Last updated on Aug 29, 2024

P = NP समस्या यह सवाल पूछती है: “यदि हम किसी समस्या के समाधान के सही होने की तेज़ी से पुष्टि (verify) कर सकते हैं, तो क्या हम उस समाधान को तेज़ी से कंप्यूट (compute) भी कर सकते हैं?” ज़्यादातर शोधकर्ताओं का मानना है कि इसका उत्तर नहीं है, यानी, P ≠ NP।

P vs NP समस्या को समझकर, हम देख सकते हैं कि ज़ीरो नॉलेज प्रूफ्स (ZKPs) कंप्यूटर विज्ञान के व्यापक क्षेत्र में कैसे फिट बैठते हैं और यह समझ सकते हैं कि ZKPs क्या कर सकते हैं और क्या नहीं।

ज़ीरो नॉलेज प्रूफ्स को P vs NP समस्या से जोड़कर “समझना” बहुत आसान है।

इस ट्यूटोरियल के तीन भाग हैं:

P vs NP समस्या की व्याख्या
समस्याओं और समाधानों को एक बूलियन फ़ॉर्मूले (Boolean formula) के रूप में व्यक्त करना
P vs NP और वे ज़ीरो नॉलेज प्रूफ्स से कैसे संबंधित हैं

पूर्वापेक्षाएँ (Prerequisites)

हम मानकर चलते हैं कि पाठक टाइम कॉम्प्लेक्सिटी (time complexity) और big $\mathcal{O}$ नोटेशन से परिचित है।

हम कहते हैं कि एक एल्गोरिदम पॉलीनोमियल टाइम (polynomial time) लेता है यदि यह $\mathcal{O}(nᶜ)$ टाइम या उससे तेज़ी से चलता है, जहाँ $n$ इनपुट का आकार है और $c$ एक नॉन-नेगेटिव कॉन्स्टेंट (non-negative constant) है। हम उन एल्गोरिदम को efficient algorithms (कुशल एल्गोरिदम) कह सकते हैं जो पॉलीनोमियल टाइम या उससे तेज़ गति से चलते हैं क्योंकि इनपुट के आकार के साथ उनका रनिंग टाइम बहुत तेज़ी से नहीं बढ़ता है।

हम कहते हैं कि एक एल्गोरिदम exponential time (घातांकीय समय) लेता है या expensive (महंगा) है यदि यह $\mathcal{O}(cⁿ)$ में चलता है जहाँ $c$ , 1 से बड़ा कॉन्स्टेंट है और $n$ इनपुट का आकार है क्योंकि इनपुट का आकार बढ़ने पर एल्गोरिदम एक्सपोनेंशियली (exponentially) धीमा हो जाता है।

भाग 1: P vs NP समस्या की व्याख्या

P में वे समस्याएँ होती हैं जिन्हें हल करना और जिनके समाधानों को वेरीफाई करना दोनों आसान होता है।

ऐसी समस्याएँ जिन्हें पॉलीनोमियल टाइम में हल किया जा सकता है और जिनके समाधानों को पॉलीनोमियल टाइम में वेरीफाई किया जा सकता है, उन्हें P की समस्याएँ (problems in P) कहा जाता है।

यहाँ कुछ ऐसी समस्याओं के उदाहरण दिए गए हैं जिनके समाधानों को कंप्यूट करना और वेरीफाई करना आसान है। ये कार्य विभिन्न पक्षों (parties) द्वारा किए जा सकते हैं, एक कंप्यूटेशन कर सकता है और दूसरा जाँच सकता है कि परिणाम वैध (valid) हैं या नहीं:

P उदाहरण 1: सूची (list) को सॉर्ट करना

हम कुशलता से एक सूची को सॉर्ट कर सकते हैं, और हम कुशलता से यह वेरीफाई भी कर सकते हैं कि सूची सॉर्ट की गई है।

हल करना (Solving): सूची को सॉर्ट करने में $\mathcal{O}(n \log n)$ टाइम लगता है (उदाहरण के लिए, mergesort का उपयोग करके), जो कि पॉलीनोमियल टाइम है। हालाँकि $n \log n$ एक पॉलीनोमियल नहीं है, लेकिन हम जानते हैं कि $\log n < n$ और इसलिए $(n \log n) < n²$ , इसलिए हमारे एल्गोरिदम का रनिंग टाइम किसी पॉलीनोमियल द्वारा ऊपर से सीमित (bounded) है, जो “पॉलीनोमियल टाइम” की आवश्यकता है।
वेरीफाई करना (Verifying): हम सूची को ट्रैवर्स (traverse) करके और यह जाँच कर कि प्रत्येक आइटम अपने बाएँ पड़ोसी से बड़ा है, यह वेरीफाई कर सकते हैं कि सूची सॉर्ट की गई है, जिसमें $\mathcal{O}(n)$ टाइम लगेगा।

P उदाहरण 2: सूची में किसी संख्या का इंडेक्स (index) वापस करना, यदि वह सूची में मौजूद है

हम कुशलता से यह खोज सकते हैं कि कोई संख्या सूची में है या नहीं और यदि हमें उसका इंडेक्स पता है तो हम यह और भी कुशलता से वेरीफाई कर सकते हैं कि संख्या मौजूद है।

हल करना (Solving): उदाहरण के लिए, दी गई सूची [8, 2, 1, 6, 7, 3] के लिए, हमें यह निर्धारित करने के लिए $\mathcal{O}(n)$ टाइम चाहिए कि क्या संख्या 7 सूची में है।
वेरीफाई करना (Verifying): लेकिन यदि हम आपको सूची देते हैं और कहते हैं कि 7 इंडेक्स 4 पर है, तो आप $\mathcal{O}(1)$ टाइम में वेरीफाई कर सकते हैं कि संख्या उस स्थिति में सूची में है। यदि हमें आइटम का स्थान नहीं बताया जाता है, तो किसी आइटम को खोजने में सामान्य स्थिति में $\mathcal{O}(n)$ टाइम लगता है क्योंकि हमें सूची में खोजना पड़ता है। यदि हमें आइटम का अनुमानित स्थान बताया जाता है, तो यह वेरीफाई करने में $\mathcal{O}(1)$ टाइम लगता है कि आइटम वास्तव में उस स्थान पर सूची में है।

P उदाहरण 3: यह निर्धारित करना कि ग्राफ में दो नोड्स जुड़े हुए हैं या नहीं

हम ब्रेड्थ-फर्स्ट सर्च (breadth-first search) का उपयोग करके कुशलता से यह निर्धारित कर सकते हैं कि ग्राफ में दो नोड्स जुड़े हुए हैं या नहीं — एक नोड से शुरू करें, फिर उन नोड्स को छोड़कर जिन्हें हम पहले ही विज़िट कर चुके हैं, उसके सभी पड़ोसियों को विज़िट करें, फिर पड़ोसियों के पड़ोसियों को खोजें, और इसी तरह आगे बढ़ें।

हल करना (Solving): ब्रेड्थ-फर्स्ट सर्च का उपयोग करके नोड्स के बीच का रास्ता खोजने में $\mathcal{O}(n + e)$ टाइम लगेगा, जहाँ $n$ ग्राफ में नोड्स की संख्या है और $e$ किनारों (edges) की संख्या है। किनारों की संख्या $e$ , $n^2$ से अधिक नहीं हो सकती है, इसलिए हम सबसे खराब स्थिति (worst case) में $\mathcal{O}(n + e)$ को $\mathcal{O}(n²)$ मान सकते हैं।
वेरीफाई करना (Verifying): हम केवल प्रस्तावित रास्ते का अनुसरण करके यह देखने के लिए कि क्या वे दो बिंदु वास्तव में उस रास्ते से जुड़े हुए हैं, $\mathcal{O}(n)$ टाइम में प्रस्तावित रास्ते के वैध होने की पुष्टि कर सकते हैं।

ऊपर दिए गए सभी उदाहरणों में, समाधान को कंप्यूट करना और वेरीफाई करना दोनों पॉलीनोमियल टाइम में किए जा सकते हैं।

द विटनेस (The Witness)

कंप्यूटर विज्ञान में एक witness (गवाह/प्रमाण) इस बात का प्रमाण है कि आपने समस्या को सही ढंग से हल किया है। ऊपर दिए गए उदाहरणों में, witness समस्या का सही उत्तर है। ऊपर दिए गए उदाहरणों के लिए, ये वे चीज़ें हैं जिन्हें हम witness के रूप में उपयोग कर सकते हैं:

सॉर्ट की गई सूची
वह इंडेक्स जहाँ सूची में संख्या दिखाई देती है
ग्राफ में दो नोड्स के बीच का रास्ता

हम बाद में देखेंगे कि यह आवश्यक नहीं है कि witness मूल समस्या का समाधान ही हो। यह उसी समस्या के वैकल्पिक प्रतिनिधित्व (alternative representation) के लिए एक समाधान भी हो सकता है।

PSPACE में समस्याएँ: सभी समस्याओं के समाधान ऐसे नहीं होते जिन्हें कुशलता से वेरीफाई किया जा सके

वे समस्याएँ जिन्हें हल करने और वेरीफाई करने के लिए घातांकीय (exponential) संसाधनों की आवश्यकता होती है, उन्हें PSPACE की समस्याएँ कहा जाता है। उन्हें PSPACE कहने का कारण यह है कि यद्यपि उन्हें हल करने में एक्सपोनेंशियल टाइम लग सकता है, लेकिन उन्हें सर्च चलाने के लिए एक्सपोनेंशियल मेमोरी स्पेस की आवश्यकता नहीं होती है।

समस्याओं के इस वर्ग (class) पर बड़े पैमाने पर शोध किया गया है, फिर भी उन्हें हल करने के लिए कोई कुशल एल्गोरिदम नहीं खोजा जा सका है। कई शोधकर्ताओं का मानना है कि इन समस्याओं को हल करने के लिए कोई कुशल एल्गोरिदम मौजूद ही नहीं है। यदि इन समस्याओं का एक कुशल समाधान खोजा जा सके, तो आधुनिक एन्क्रिप्शन (encryption) को तोड़ने और कंप्यूटिंग को मूल रूप से बदलने के लिए एल्गोरिदम का पुन: उपयोग करना भी संभव होगा जैसा कि हम इसे जानते हैं।

इन समस्याओं के कुशल समाधान खोजने के लिए महत्वपूर्ण प्रोत्साहनों के बावजूद, साक्ष्य बताते हैं कि ऐसे समाधान संभवतः मौजूद नहीं हैं। ये समस्याएँ इतनी चुनौतीपूर्ण हैं कि यदि आप उन्हें सही ढंग से हल भी कर लेते हैं तो भी आप आसानी से वेरीफाई करने योग्य प्रमाण (witness) प्रदान नहीं कर सकते।

PSPACE में समस्याओं के उदाहरण

PSPACE उदाहरण 1: शतरंज (Chess) की इष्टतम (optimal) चाल खोजना

मान लीजिए कि हम एक शक्तिशाली कंप्यूटर से पूछते हैं, “मोहरों की इस स्थिति वाले इस शतरंज बोर्ड को देखते हुए, अगली इष्टतम चाल क्या है?”

कंप्यूटर उत्तर देता है “काले प्यादे (pawn) को f4 से f3 पर ले जाएँ।”

आप कैसे भरोसा कर सकते हैं कि कंप्यूटर आपको सही उत्तर दे रहा है?

जाँचने का कोई कुशल तरीका नहीं है — आपको वही काम करना होगा जो कंप्यूटर ने किया था। इसमें बोर्ड की सभी संभावित भविष्य की स्थितियों (states) के माध्यम से पूरी खोज (full search) करना शामिल है। ऐसा कोई witness नहीं है जो कंप्यूटर हमें प्रदान कर सके जिससे हम यह पुष्टि कर सकें कि “काले प्यादे को f4 से f3 पर ले जाएँ” वास्तव में अगली सबसे अच्छी चाल है। इस तरह, इस समस्या की प्रकृति पहले चर्चा किए गए उदाहरणों से बहुत अलग है: हम कुशलता से यह वेरीफाई नहीं कर सकते हैं कि दावा की गई इष्टतम चाल वास्तव में इष्टतम चाल है।

इस उदाहरण में, कंप्यूटर द्वारा प्रस्तुत “witness” में भविष्य की सभी संभावित गेम स्थितियाँ (game states) शामिल हैं। हालाँकि, इस डेटा की भारी मात्रा इसके समाधान की सटीकता को कुशलता से वेरीफाई करना व्यावहारिक रूप से असंभव बना देती है।

PSPACE उदाहरण 2: यह निर्धारित करना कि क्या रेगेक्स (regular expressions) समतुल्य (equivalent) हैं

दो रेगेक्स, a+ और aa*, समान स्ट्रिंग्स से मेल खाते हैं। यदि कोई स्ट्रिंग पहले रेगेक्स से मेल खाती है, तो वह दूसरे से भी मेल खाएगी, और इसके विपरीत भी।

हालाँकि, यह जाँचना कि क्या दो arbitrary रेगेक्स समतुल्य हैं, कंप्यूट करने में एक्सपोनेंशियल टाइम लेता है। भले ही एक शक्तिशाली कंप्यूटर आपको बताए कि वे समान स्ट्रिंग्स से मेल खाते हैं, फिर भी कंप्यूटर द्वारा आपको यह दिखाने के लिए कोई छोटा प्रमाण (witness) नहीं दिया जा सकता कि उत्तर सही हैं। शतरंज के उदाहरण के समान, आपको यह जाँचने के लिए स्ट्रिंग्स के बहुत बड़े स्पेस को खोजना होगा कि क्या रेगेक्स समतुल्य हैं, और उसमें एक्सपोनेंशियल टाइम लगेगा।

शतरंज और रेगेक्स समतुल्यता दोनों में एक सामान्य विशेषता है कि दोनों को उत्तर खोजने के लिए एक्सपोनेंशियल संसाधनों की आवश्यकता होती है और उत्तरों को वेरीफाई करने के लिए एक्सपोनेंशियल संसाधनों की आवश्यकता होती है।

PSPACE से भी अधिक कम्प्यूटेशनल रूप से गहन समस्याएँ

कुछ समस्याएँ इतनी कठिन होती हैं कि उन्हें हल करने के लिए एक्सपोनेंशियल टाइम और एक्सपोनेंशियल मेमोरी की आवश्यकता होती है, लेकिन वे समस्याएँ आमतौर पर सैद्धांतिक होती हैं और वास्तविक दुनिया में अक्सर दिखाई नहीं देती हैं।

ऐसी समस्या का एक उदाहरण एक ऐसे नियम के साथ चेकर्स (Checkers) है कि मोहरे कभी भी ऐसी स्थिति में नहीं जा सकते जो बोर्ड की पिछली स्थिति को फिर से बनाए। यह सुनिश्चित करने के लिए कि हम संभावित चालों के स्पेस को एक्सप्लोर करते समय गेम के लिए बोर्ड की स्थिति को न दोहराएँ, हमें उन सभी बोर्ड स्थितियों का ट्रैक रखना होगा जो पहले ही विज़िट की जा चुकी हैं। चूँकि गेम की लंबाई बोर्ड के आकार में एक्सपोनेंशियल हो सकती है, इसलिए मेमोरी की आवश्यकताएँ भी एक्सपोनेंशियल होती हैं।

NP में समस्याएँ: कुछ समस्याओं को जल्दी से वेरीफाई किया जा सकता है लेकिन जल्दी से कंप्यूट नहीं किया जा सकता

यदि हम किसी समस्या के समाधान को तेज़ी से वेरीफाई कर सकते हैं, तो वह समस्या NP में है। हालाँकि, समाधान खोजने के लिए एक्सपोनेंशियल संसाधनों की आवश्यकता हो सकती है।

कोई भी समस्या जिसके प्रस्तावित समाधान (witness) को सही के रूप में तेज़ी से वेरीफाई किया जा सकता है, वह एक NP समस्या है। यदि समस्या में पॉलीनोमियल टाइम में समाधान खोजने के लिए कोई एल्गोरिदम भी है, तो यह एक P समस्या है। सभी P समस्याएँ NP समस्याएँ हैं, लेकिन यह बेहद असंभव है कि सभी NP समस्याएँ भी P समस्याएँ हों।

NP में समस्याओं के उदाहरण। इन्हें नीचे अधिक विस्तार से समझाया गया है:

सुडोकू (Sudoku) पहेली के समाधान की गणना करना — सुडोकू पहेली के प्रस्तावित समाधान को वेरीफाई करना।
मानचित्र की 3-कलरिंग (3-coloring) की गणना करना (यदि यह मौजूद है) — मानचित्र की प्रस्तावित 3-कलरिंग को वेरीफाई करना।
बूलियन फ़ॉर्मूले (Boolean formula) के लिए एक असाइनमेंट खोजना जिसका परिणाम ‘true’ (सत्य) हो — यह वेरीफाई करना कि प्रस्तावित असाइनमेंट फ़ॉर्मूले का परिणाम ‘true’ देता है।

नोट: NP का अर्थ नॉन-डिटरमिनिस्टिक पॉलीनोमियल (non-deterministic polynomial) है। हम इस शब्दजाल में नहीं पड़ेंगे कि वह नाम कहाँ से आया; हम केवल नाम इसलिए दे रहे हैं ताकि पाठक गलती से यह न सोचे कि इसका अर्थ “नॉट पॉलीनोमियल टाइम” है।

NP में समस्याओं के उदाहरण

NP उदाहरण 1: सुडोकू (Sudoku)

सुडोकू गेम में, खिलाड़ी को कुछ भरे हुए नंबरों के साथ $9 \times 9$ का ग्रिड दिया जाता है। खिलाड़ी का लक्ष्य ग्रिड के बाकी हिस्से को 1-9 नंबरों से भरना होता है ताकि कोई भी नंबर किसी भी पंक्ति, कॉलम या $3 \times 3$ बॉक्स (जो गहरी रेखाओं द्वारा उल्लिखित हैं) में एक से अधिक बार न आए। Wikipedia की निम्नलिखित छवियाँ इसे स्पष्ट करती हैं। पहली छवि में, हम खिलाड़ी को दिए गए 9x9 ग्रिड को देखते हैं। दूसरी छवि में, हम खिलाड़ी का समाधान देखते हैं।

सुडोकू पहेली का solution दिए जाने पर, हम कॉलम, पंक्तियों और $3\times 3$ सबग्रिड पर लूप करके तेज़ी से वेरीफाई कर सकते हैं कि समाधान सही है। witness को पॉलीनोमियल टाइम में वेरीफाई किया जा सकता है।

हालाँकि, समाधान को computing (कंप्यूट करने) के लिए काफी अधिक संसाधनों की आवश्यकता होती है — खोजने के लिए संयोजनों (combinations) की एक एक्सपोनेंशियल संख्या होती है। $9\times 9$ ग्रिड के लिए, कंप्यूटर के लिए यह मुश्किल नहीं है। हालाँकि, यदि हम सुडोकू पहेली को मनमाने ढंग से बड़ा होने देते हैं: प्रत्येक पक्ष का आकार $n$ है, जहाँ $n$ , 9 का गुणक (multiple) है। उस स्थिति में, समाधान खोजने की कठिनाई $n$ के साथ एक्सपोनेंशियली बढ़ती है।

NP उदाहरण 2: मानचित्र की थ्री-कलरिंग (Three-coloring)

क्षेत्रों के किसी भी 2D मानचित्र को केवल चार रंगों से “रंगा” जा सकता है (देखें four color theorem)। अर्थात, हम प्रत्येक क्षेत्र को एक अद्वितीय रंग (चार रंगों में से एक) इस प्रकार असाइन कर सकते हैं कि कोई भी पड़ोसी क्षेत्र एक ही रंग साझा न करे। उदाहरण के लिए, निम्नलिखित छवि (Wikipedia से) संयुक्त राज्य अमेरिका को चार रंगों: गुलाबी, हरे, पीले और लाल रंग से रंगा हुआ दिखाती है। यह वेरीफाई करने के लिए कुछ क्षण दें कि किन्हीं दो स्पर्श करने वाले राज्यों को एक ही रंग नहीं दिया गया है:

थ्री-कलरिंग समस्या यह पूछती है कि क्या चार के बजाय केवल तीन रंगों का उपयोग करके मानचित्र को रंगा जा सकता है। एक थ्री-कलरिंग (यदि यह मौजूद है) खोजना एक कम्प्यूटेशनल रूप से गहन सर्च समस्या है। हालाँकि, एक proposed (प्रस्तावित) 3-कलरिंग को वेरीफाई करना आसान है: प्रत्येक क्षेत्र से लूप करें और जाँचें कि किसी भी पड़ोसी क्षेत्र का रंग वर्तमान में जाँचे जा रहे क्षेत्र के समान नहीं है।

यह पता चलता है कि संयुक्त राज्य अमेरिका को 3-कलर करना संभव नहीं है।

किसी विशेष मानचित्र को 3 कलर न कर पाने के कारण अलग-अलग हो सकते हैं, लेकिन संयुक्त राज्य अमेरिका के मामले में, नेवादा (नीचे दिए गए मानचित्र में लाल (red) क्षेत्र) पाँच क्षेत्रों से घिरा है। हम नेवादा को एक रंग से रंगते हैं, फिर हमें इसके पड़ोसी क्षेत्रों के रंगों को वैकल्पिक (alternate) करना होगा। हालाँकि, जब हम नेवादा के पड़ोसियों का चक्कर पूरा कर लेंगे, तो हम एक ऐसे क्षेत्र के साथ समाप्त होंगे जिसकी सीमाओं पर तीन रंगों वाले पड़ोसी होंगे, जिससे बिना रंगे हुए क्षेत्र के लिए कोई वैध रंग नहीं बचेगा।

यदि आप इस समस्या के बारे में अधिक जानना चाहते हैं तो 3-कलरिंग मानचित्रों के बारे में यहाँ एक quick and interesting video about 3-coloring maps है।

हालाँकि, ऑस्ट्रेलिया को 3-कलर करना संभव है:

सभी मानचित्रों को तीन रंगों में नहीं रंगा जा सकता। एक मनमाने 2D मानचित्र के लिए एक थ्री-कलरिंग कंप्यूट करना, यदि यह मौजूद है, कुशलता से नहीं किया जा सकता है — इसमें आमतौर पर एक ब्रूट-फोर्स सर्च (brute-force search) की आवश्यकता होती है जिसमें एक्सपोनेंशियल टाइम लग सकता है।

हालाँकि, यदि कोई थ्री-कलरिंग हल करता है, तो उनके समाधान को वेरीफाई करना आसान है।

P, NP, और PSPACE के बीच संबंध

प्रत्येक वर्ग (class) के लिए कम्प्यूटेशनल संसाधन

नीचे दी गई तालिका समस्या के प्रत्येक वर्ग के लिए आवश्यक कम्प्यूटेशनल संसाधनों का सारांश देती है:

श्रेणी (Category)	कंप्यूट टाइम (Compute Time)	वेरिफिकेशन टाइम (Verification Time)
P	पॉलीनोमियल या बेहतर होना चाहिए	पॉलीनोमियल या बेहतर होना चाहिए
NP	कोई आवश्यकता नहीं	पॉलीनोमियल या बेहतर होना चाहिए
PSPACE	कोई आवश्यकता नहीं	कोई आवश्यकता नहीं

P, NP, और PSPACE के बीच कठिनाई का पदानुक्रम (Hierarchy of Difficulty)

कोई भी समस्या जिसके witness को वेरीफाई करने के लिए एक्सपोनेंशियल संसाधनों की आवश्यकता होती है, वह एक PSPACE (या कठिन समस्या) है। यदि किसी के पास PSPACE समस्याओं के लिए witnesses को वेरीफाई करने के लिए एक्सपोनेंशियल संसाधन हैं, तो वह व्यक्ति किसी भी P या NP समस्या के समाधान की गणना आसानी से कर सकता है। इसलिए, सभी P और NP समस्याएँ PSPACE समस्याओं का एक सबसेट (subset) हैं, जैसा कि नीचे दिए गए चित्र में दिखाया गया है।

दूसरे शब्दों में, यदि आपके पास बड़े सर्कल में समस्याओं के एक वर्ग को हल करने या वेरीफाई करने के लिए पर्याप्त शक्तिशाली कंप्यूटर है, तो आप इसके एक सबसेट को हल या वेरीफाई कर सकते हैं:

P vs NP समस्या

P उन समस्याओं का वर्ग है जिन्हें कुशलता से हल और वेरीफाई किया जा सकता है, जबकि NP उन समस्याओं का वर्ग है जिन्हें कुशलता से वेरीफाई किया जा सकता है। “P vs NP” प्रश्न बस यह पूछता है कि क्या ये दोनों वर्ग समान हैं।

यदि P = NP है, तो इसका मतलब यह होगा कि जब भी हम किसी समाधान को वेरीफाई करने के लिए एक कुशल तरीका खोज सकते हैं, तो हम उस समाधान को खोजने के लिए एक कुशल तरीका भी खोज सकते हैं। याद रखें कि समाधान खोजना हमेशा उसे वेरीफाई करने जितना ही कठिन होता है। (परिभाषा के अनुसार, किसी समस्या को हल करने में सही उत्तर खोजना शामिल है, जिसका अर्थ है कि समस्या को हल करने वाला एल्गोरिदम प्रक्रिया में अपने उत्तर को वेरीफाई भी कर रहा है)।

यदि P = NP सत्य है, तो इसका मतलब है कि सुडोकू पहेलियों (मनमाने आकार की) को कंप्यूट करने और थ्री कलरिंग मौजूद है या नहीं यह खोजने के लिए एक कुशल एल्गोरिदम है। इसका मतलब यह भी है कि अधिकांश आधुनिक क्रिप्टोग्राफ़िक एल्गोरिदम को तोड़ने के लिए एक कुशल एल्गोरिदम मौजूद है।

वर्तमान में, यह अप्रमाणित है कि P और NP समान सेट हैं या नहीं। यद्यपि NP समस्याओं के लिए कुशल एल्गोरिदम खोजने के कई प्रयास किए गए हैं, सभी साक्ष्य बताते हैं कि ऐसे एल्गोरिदम मौजूद नहीं हैं।

इसी तरह, PSPACE समस्याओं के लिए कुशल समाधान या सत्यापन तंत्र (verification mechanisms) मौजूद हैं या नहीं, यह प्रश्न खुला है। हालाँकि शोधकर्ताओं का व्यापक अनुमान है कि P ≠ NP और NP ≠ PSPACE, इन निष्कर्षों के लिए कोई औपचारिक गणितीय प्रमाण मौजूद नहीं है। इसलिए, व्यापक प्रयासों के बावजूद, NP समस्याओं के लिए कुशल समाधान और PSPACE समस्याओं के लिए कुशल सत्यापन विधियाँ खोजी नहीं जा सकी हैं।

व्यावहारिक उद्देश्यों के लिए, हम मान सकते हैं कि P ≠ NP और NP ≠ PSPACE। वास्तव में, जब हम आधुनिक क्रिप्टोग्राफी एल्गोरिदम पर महत्वपूर्ण डेटा का भरोसा करते हैं तो हम परोक्ष रूप से यही धारणा बनाते हैं।

भाग 2: समस्याओं और समाधानों को बूलियन फ़ॉर्मूले (Boolean formulas) के रूप में व्यक्त करना

P और NP समस्याओं को जो चीज़ एक साथ बाँधती है वह यह है कि उनके समाधान को तेज़ी से वेरीफाई किया जा सकता है। यह अत्यंत उपयोगी होगा यदि हम उन सभी (P और NP) समस्याओं और उनके समाधानों को एक सामान्य भाषा में वर्णित कर सकें। यानी, हम समस्या का एक ऐसा एन्कोडिंग (encoding) चाहते हैं जो एक सूची को सॉर्ट किए गए साबित करने से लेकर, सुडोकू पहेली को हल किए गए साबित करने तक, यह साबित करने तक कि हमारे पास एक थ्री कलरिंग है, जैसी विविध समस्याओं के लिए काम करे।

NP या P में किसी समस्या के समाधान को वेरीफाई करना, एक बूलियन फ़ॉर्मूले के समाधान को वेरीफाई करके पूरा किया जा सकता है जो समस्या को मॉडल करता है।

“एक बूलियन फ़ॉर्मूला जो समस्या को मॉडल करता है” से हमारा क्या मतलब है, यह स्पष्ट हो जाएगा जब हम यह वर्णन करेंगे कि “एक बूलियन फ़ॉर्मूले के समाधान” से हमारा क्या मतलब है और बूलियन फ़ॉर्मूले के साथ कुछ उदाहरण मॉडलिंग समस्याओं को देखेंगे।

एक बूलियन फ़ॉर्मूले (Boolean formula) के समाधान

एक बूलियन फ़ॉर्मूले को व्यक्त करने के लिए, हम ऑपरेटर $¬$ का उपयोग बूलियन NOT होने के लिए, $∧$ का उपयोग बूलियन AND होने के लिए, और $∨$ का उपयोग बूलियन OR होने के लिए करते हैं। उदाहरण के लिए, $a ∧ b$ true का मूल्यांकन (evaluates to true) करता है यदि और केवल यदि $a$ और $b$ दोनों true हों। $a ∧ ¬b$ true का मूल्यांकन करता है यदि और केवल यदि $a$ , true है और $b$ , false है।

मान लीजिए कि हमारे पास बहुत सारे बूलियन चर (variables) $x₁$ , $x₂$ , $x₃$ , $x₄$ हैं और एक बूलियन फ़ॉर्मूला है:

out = (x₁ ∨ ¬x₂ ∨ ¬ x₃) ∧ (¬x₂ ∨ x₃ ∨ x₄) ∧ (x₁ ∨ x₃ ∨ ¬x₄) ∧ (¬x₂ ∨ ¬x₃∨ ¬x₄)

प्रश्न यह है: क्या हम $x₁, x₂, x₃, x₄$ के लिए ऐसे मान (values) पा सकते हैं कि $out$ , true हो? उपरोक्त फ़ॉर्मूले के लिए, हम पा सकते हैं। true के लिए $T$ और false के लिए $F$ लिखते हुए, हम अपना समाधान इस प्रकार लिख सकते हैं:

\begin{align*} x₁ = T \\ x₂ = F \\ x₃ = T \\ x₄ = F \end{align*}

समाधान को फ़ॉर्मूले में रखने पर यह प्राप्त होता है:

\begin{align*} x₁ &= T \\ x₂ &= F \\ x₃ &= T \\ x₄ &= F \\ out &= (x₁ ∨ ¬x₂ ∨ ¬ x₃) ∧ (¬x₂ ∨ x₃ ∨ x₄) ∧ (x₁ ∨ x₃ ∨ ¬x₄)∧ (¬x₂ ∨ ¬x₃∨ ¬x₄) \\ out &= (T ∨ ¬ F ∨ ¬ T) ∧ (¬ F ∨ T ∨ F) ∧ (T ∨ T ∨ ¬ F) ∧ (¬ F ∨ ¬ T ∨ ¬ F) \\ &= (T) ∧ (T) ∧ (T) ∧ (T) \\ &= T \\ \end{align*}

इसे वेरीफाई करना आसान था, लेकिन बहुत बड़े बूलियन फ़ॉर्मूले के लिए समाधान खोजने में एक्सपोनेंशियल टाइम लग सकता है। एक बूलियन फ़ॉर्मूले का समाधान खोजना अपने आप में एक NP समस्या है — समाधान खोजने के लिए एक्सपोनेंशियल संसाधनों की आवश्यकता हो सकती है, लेकिन इसे वेरीफाई करना पॉलीनोमियल टाइम में किया जा सकता है।

लेकिन हमें इस बात पर ज़ोर देना चाहिए: बूलियन फ़ॉर्मूले का हमारा उपयोग उन्हें हल करने के लिए नहीं है — केवल उनके लिए प्रस्तावित समाधानों को वेरीफाई करने के लिए है।

P और NP की सभी समस्याओं को उन्हें बूलियन फ़ॉर्मूले में बदलकर और फ़ॉर्मूले का समाधान दिखाकर वेरीफाई किया जा सकता है

निम्नलिखित उदाहरणों में, इनपुट एक P या NP समस्या है और आउटपुट एक बूलियन फ़ॉर्मूला है। यदि हम मूल समस्या का समाधान जानते हैं, तो हम बूलियन फ़ॉर्मूले का समाधान भी जानेंगे।

हमारा इरादा यह दिखाना है कि हम मूल समस्या के लिए witness को जानते हैं — लेकिन बूलियन रूप में।

उदाहरण 1: बूलियन फ़ॉर्मूले का उपयोग करके जाँचना कि क्या कोई सूची सॉर्ट की गई है

एक-बिट बाइनरी नंबर $A$ और $B$ पर विचार करें। निम्नलिखित ट्रुथ टेबल (truth table) true लौटाती है जब $A > B$ :

A	B	A > B
0	0	0
0	1	0
1	0	1
1	1	0

कॉलम $A > B$ को $A ∧ ¬B$ अभिव्यक्ति के साथ मॉडल किया जा सकता है, जो केवल उसी पंक्ति में true लौटाता है जहाँ $A > B$ एक है।

अब एक ऐसी टेबल पर विचार करें जो $A = B$ व्यक्त करती है:

A	B	A = B
0	0	1
0	1	0
1	0	0
1	1	1

कॉलम $A = B$ को $(A ∧ B) ∨ ¬(A ∨ B)$ अभिव्यक्ति के साथ मॉडल किया जा सकता है। $(A ∧ B)$ true लौटाता है जब $A = 1$ और $B = 1$ होता है और $¬(A ∨ B)$ true लौटाता है जब $A$ और $B$ दोनों शून्य होते हैं।

एक बिट नंबरों के लिए अभिव्यक्तियाँ (expressions):

\begin{align*} A > B &\rightarrow A ∧ ¬B \\ A = B &\rightarrow (A ∧ B) ∨ ¬(A ∨ B) \end{align*}

जल्द ही काम आएँगी।

अब हम एक बिट से अधिक के बाइनरी नंबरों की तुलना कैसे करें?

सबसे महत्वपूर्ण भिन्न बिट (most significant different bit) द्वारा बाइनरी तुलना

मान लीजिए कि आप दोनों नंबरों के सबसे बाएँ Most Significant Bit (MSB) से शुरू करते हैं और दाएँ Least Significant Bit (LSB) की ओर बढ़ते हैं। पहले बिट पर, जहाँ दोनों नंबर भिन्न होते हैं:

यदि उस बिट पर $P$ का मान $1$ है और $Q$ का मान $0$ है, तो $P ≥ Q$ ।
निम्नलिखित एनीमेशन $P ≥ Q$ का पता लगाने वाले एल्गोरिदम को स्पष्ट करता है:

यदि $P = Q$ है, तो सभी बिट्स बराबर हैं। $P = Q$ का अर्थ है कि $P ≥ Q$ भी सत्य है:

यदि P < Q है, तो हम पहले बिट पर इसका पता लगा लेंगे जहाँ Q, 1 है और P, 0 है:

मान लीजिए, व्यापकता खोए बिना (without loss of generality), कि हम $P$ में बिट्स को $p₄, p₃, p₂, p₁$ और $Q$ में बिट्स को $q₄, q₃, q₂, q₁$ के रूप में नंबर देते हैं।

यदि $P ≥ Q$ तो निम्नलिखित में से एक सत्य होना चाहिए:

$p₄ > q₄$
$p₄ = q₄$ और $p₃ > q₃$
$p₄ = q₄$ और $p₃ = q₃$ और $p₂ > q₂$
$p₄ = q₄$ और $p₃ = q₃$ और $p₂ = q₂$ और $(p₁ > q₁ \text{ or } p₁ = q₁)$

हम बुलेट पॉइंट को एक एकल समीकरण में जोड़ सकते हैं।

\begin{align*} &((p₄ > q₄)) ∨ \\ &((p₄ = q₄) ∧ (p₃ > q₃)) ∨ \\ &((p₄ = q₄) ∧ (p₃ = q₃) ∧ (p₂ > q₂)) ∨ \\ &((p₄ = q₄) ∧ (p₃ = q₃) ∧ (p₂ = q₂) ∧ ((p₁ > q₁) ∨ (p₁ = q₁))) \end{align*}

हमारे बूलियन अभिव्यक्तियों को याद करें जिन्होंने एक बिट समानता और तुलना को मॉडल किया था:

\begin{align*} A > B &== A ∧ ¬B\\ A = B &== (A ∧ B) ∨ ¬(A ∨ B) \end{align*}

हम $A > B$ और $A = B$ फ़ॉर्मूले के लिए अभिव्यक्तियों को ऊपर दिए गए समीकरण में प्रतिस्थापित (substitute) कर सकते हैं। बहुत ज़्यादा गणित से बचने के लिए, हम नीचे वीडियो के रूप में संचालन (operations) दिखाते हैं:

अंतिम बूलियन फ़ॉर्मूला जो 4 बिट्स के लिए $P ≥ Q$ व्यक्त करता है, वह है:

\begin{align*} &(p₄ ∧ ¬q₄) ∨ \\ &(((p₄ ∧ q₄) ∨ ¬(p₄ ∨ q₄)) ∧ (p₃ ∧ ¬q₃)) ∨ \\ &(((p₄ ∧ q₄) ∨ ¬(p₄ ∨ q₄)) ∧ ((p₃ ∧ q₃) ∨ ¬(p₃ ∨ q₃)) ∧ (p₂ ∧ ¬q₂)) ∨ \\ &(((p₄ ∧ q₄) ∨ ¬(p₄ ∨ q₄)) ∧ ((p₃ ∧ q₃) ∨ ¬(p₃ ∨ q₃)) ∧ ((p₂ ∧ q₂) ∨ ¬(p₂ ∨ q₂)) ∧ ((p₁ ∧ ¬q₁) ∨ ((p₁ ∧ q₁) ∨ ¬(p₁ ∨ q₁)))) \end{align*}

आइए एक बूलियन अभिव्यक्ति जो ऊपर वर्णित तरीके से दो बाइनरी नंबरों की तुलना करती है, उसे
“तुलना अभिव्यक्ति (comparison expression)” कहें।

जाँचना कि क्या कोई सूची सॉर्ट की गई है

एक निश्चित आकार के नंबरों की तुलना करने के लिए दिए गए बूलियन फ़ॉर्मूले के साथ, हम सूची में आसन्न (adjacent) तत्वों के प्रत्येक जोड़े पर तुलना अभिव्यक्ति को बार-बार लागू कर सकते हैं और AND ऑपरेशन का उपयोग करके तुलना अभिव्यक्तियों को जोड़ सकते हैं। सूची तभी और केवल तभी सॉर्ट की गई है जब सभी तुलना अभिव्यक्तियों का AND, true हो।

इस प्रकार, हम देखते हैं कि सूची को सॉर्ट किए गए साबित करने वाला witness, सॉर्ट की गई सूची ही होना ज़रूरी नहीं है। यह उस बूलियन फ़ॉर्मूले का इनपुट भी हो सकता है जिसे हमने ऊपर बनाया है जिसके परिणामस्वरूप फ़ॉर्मूला true लौटाता है।

उदाहरण 2: बूलियन फ़ॉर्मूले के रूप में एक 3-कलरिंग

आइए एक बार फिर ऑस्ट्रेलिया के हमारे मानचित्र को देखें:

समाधान को बूलियन फ़ॉर्मूले के रूप में मॉडल करने के लिए, फ़ॉर्मूले को निम्नलिखित तथ्यों को एन्कोड करना होगा:

प्रत्येक क्षेत्र में तीन रंगों में से एक रंग है
प्रत्येक क्षेत्र का रंग उसके पड़ोसी से अलग है

उदाहरण के लिए, यह कहने के लिए कि पश्चिमी ऑस्ट्रेलिया (Western Australia) या तो हरा, नीला या लाल है, हमें तीन चर WESTERN_AUSTRALIA_GREEN, WESTERN_AUSTRALIA_BLUE, WESTERN_AUSTRALIA_RED बनाने होंगे। लंबे चर नामों से बचने के लिए, आइए इसे WA_G, WA_B, और WA_R कहें। हमारा बूलियन फ़ॉर्मूला तब है:

(WA_G ∧ ¬WA_B ∧ ¬WA_R) ∨ (¬WA_G ∧ WA_B ∧ ¬WA_R) ∨ (¬WA_G ∧ ¬WA_B ∧ WA_R)

दूसरे शब्दों में:

"(West Australia हरा (green) है और West Australia नीला (blue) नहीं है और West Australia लाल (red) नहीं है)

या (OR)

(West Australia हरा (green) नहीं है और West Australia नीला (blue) है और West Australia लाल (red) नहीं है)

या (OR)

(West Australia हरा (green) नहीं है और West Australia नीला (blue) नहीं है और West Australia लाल (red) है)"

ज़ोर देने के लिए बूलियन फ़ॉर्मूले को रंगना:

(WA_G ∧ ¬WA_B ∧ ¬WA_R) ∨ (¬WA_G ∧ WA_B ∧ ¬WA_R) ∨ (¬WA_G ∧ ¬WA_B ∧ WA_R)

आइए उपरोक्त फ़ॉर्मूले को color assignment constraint कहें।

हम किसी क्षेत्र के असाइन किए गए रंग को एन्कोड करने के लिए बूलियन चरों का उपयोग करते हैं। चूँकि एक बूलियन चर केवल दो मान धारण कर सकता है, लेकिन एक क्षेत्र तीन रंगों में से एक हो सकता है, इसलिए प्रत्येक क्षेत्र को तीन बूलियन चर असाइन किए जाते हैं, प्रत्येक रंग के लिए एक। यदि किसी क्षेत्र को एक विशेष रंग असाइन किया जाता है, तो संबंधित चर सत्य (true) पर सेट होता है और अन्य असत्य (false) पर सेट होते हैं।

उपरोक्त फ़ॉर्मूला सत्य है यदि और केवल यदि पश्चिमी ऑस्ट्रेलिया क्षेत्र को ठीक एक रंग असाइन किया गया हो।

पड़ोसी रंग की बाधा (Neighboring color constraint)

इसके बाद, हम एक फ़ॉर्मूला लिखना चाहते हैं जो यह व्यक्त करे कि WA का रंग उसके पड़ोसी से अलग है। हम WA की तरह ही SA (दक्षिण ऑस्ट्रेलिया) के लिए तीन चर बनाते हैं। अब, हमारा फ़ॉर्मूला केवल यह कहता है, “प्रत्येक रंग के लिए, WA और SA दोनों वह रंग नहीं हैं”। यह कहने के समतुल्य (equivalent) है “WA और SA एक ही रंग के नहीं हैं।” आइए दक्षिण ऑस्ट्रेलिया (जो पश्चिमी ऑस्ट्रेलिया का पड़ोसी है) के रंग असाइनमेंट को संदर्भित करने के लिए चर नामों SA_G, SA_B, और SA_R का उपयोग करें। हम यह व्यक्त करने के लिए नीचे दिए गए फ़ॉर्मूले का उपयोग करते हैं कि उनके अलग-अलग रंग हैं:

¬(WA_G ∧ SA_G) ∧ ¬(WA_B ∧ SA_B) ∧ ¬(WA_R ∧ SA_R)

दूसरे शब्दों में:

यह ऐसा नहीं (NOT) है कि (West Australia हरा (green) है और South Australia हरा (green) है)

और (AND)

यह ऐसा नहीं (NOT) है कि (West Australia नीला (blue) है और South Australia नीला (blue) है)

और (AND)

यह ऐसा नहीं (NOT) है कि (West Australia लाल (red) है और South Australia लाल (red) है)"

उपरोक्त फ़ॉर्मूला संतुष्ट होगा यदि और केवल यदि पश्चिमी ऑस्ट्रेलिया और दक्षिण ऑस्ट्रेलिया को एक ही रंग नहीं दिया गया था। आइए उपरोक्त फ़ॉर्मूले को boundary constraint कहें।

हमें प्रत्येक क्षेत्र पर कलर असाइनमेंट कंस्ट्रेंट और पड़ोसियों के प्रत्येक जोड़े पर अलग-अलग कलर कंस्ट्रेंट लागू करने की आवश्यकता है, फिर सभी कंस्ट्रेंट्स को एक साथ AND करना होगा।

ऑस्ट्रेलिया की 3-कलरिंग को मॉडल करने के लिए एक फ़ॉर्मूला

अब हम अंतिम बूलियन फ़ॉर्मूला दिखाते हैं जो ऑस्ट्रेलिया के लिए एक वैध 3 कलरिंग को वेरीफाई करता है। यहाँ लेबल किए गए क्षेत्र हैं:

सबसे पहले, हम प्रत्येक क्षेत्र को एक चर नाम असाइन करते हैं:

WA = West Australia
SA = South Australia
NT = Northern Territory
Q = Queensland
NSW = New South Wales
V = Victoria

कलर कंस्ट्रेंट्स: छह क्षेत्रों में से प्रत्येक का ठीक एक रंग है:

(WA_G ∧ ¬WA_B ∧ ¬WA_R) ∨ (¬WA_G ∧ WA_B ∧ ¬WA_R) ∨ (¬WA_G ∧ ¬WA_B ∧ WA_R)
(SA_G ∧ ¬SA_B ∧ ¬SA_R) ∨ (¬SA_G ∧ SA_B ∧ ¬SA_R) ∨ (¬SA_G ∧ ¬SA_B ∧ SA_R)
(NT_G ∧ ¬NT_B ∧ ¬NT_R) ∨ (¬NT_G ∧ NT_B ∧ ¬NT_R) ∨ (¬NT_G ∧ ¬NT_B ∧ NT_R)
(Q_G ∧ ¬Q_B ∧ ¬Q_R) ∨ (¬Q_G ∧ Q_B ∧ ¬Q_R) ∨ (¬Q_G ∧ ¬Q_B ∧ Q_R)
(NSW_G ∧ ¬NSW_B ∧ ¬NSW_R) ∨ (¬NSW_G ∧ NSW_B ∧ ¬NSW_R) ∨ (¬NSW_G ∧ ¬NSW_B ∧ NSW_R)
(V_G ∧ ¬V_B ∧ ¬V_R) ∨ (¬V_G ∧ V_B ∧ ¬V_R) ∨ (¬V_G ∧ ¬V_B ∧ V_R)

बाउंड्री कंस्ट्रेंट्स: प्रत्येक पड़ोसी क्षेत्र एक रंग साझा नहीं करता है

इसके बाद, हम सीमाओं (boundaries) के माध्यम से पुनरावृति (iterate) करते हैं और उन पड़ोसियों के लिए एक बाउंड्री कंस्ट्रेंट कंप्यूट करते हैं। नीचे दिया गया वीडियो एल्गोरिदम को काम करते हुए दिखाता है। हम वीडियो के बाद बाउंड्री कंडीशन के लिए फ़ार्मुलों का अंतिम सेट दिखाते हैं:

Western Australia और South Australia:

¬(WA_G ∧ SA_G) ∧ ¬(WA_B ∧ SA_B) ∧ ¬(WA_R ∧ SA_R)

Western Australia और Northern Territory:

¬(WA_G ∧ NT_G) ∧ ¬(WA_B ∧ NT_B) ∧ ¬(WA_R ∧ NT_R)

Northern Territory और South Australia:

¬(NT_G ∧ SA_G) ∧ ¬(NT_B ∧ SA_B) ∧ ¬(NT_R ∧ SA_R)

Northern Territory और Queensland:

¬(NT_G ∧ Q_G) ∧ ¬(NT_B ∧ Q_B) ∧ ¬(NT_R ∧ Q_R)

South Australia और Queensland:

¬(SA_G ∧ Q_G) ∧ ¬(SA_B ∧ Q_B) ∧ ¬(SA_R ∧ Q_R)

South Australia और New South Wales:

¬(SA_G ∧ NSW_G) ∧ ¬(SA_B ∧ NSW_B) ∧ ¬(SA_R ∧ NSW_R)

South Australia और Victoria:

¬(SA_G ∧ V_G) ∧ ¬(SA_B ∧ V_B) ∧ ¬(SA_R ∧ V_R)

Queensland और New South Wales:

¬(Q_G ∧ NSW_G) ∧ ¬(Q_B ∧ NSW_B) ∧ ¬(Q_R ∧ NSW_R)

New South Wales और Victoria:

¬(NSW_G ∧ V_G) ∧ ¬(NSW_B ∧ V_B) ∧ ¬(NSW_R ∧ V_R)

हम ऊपर बताए गए 15 फ़ार्मुलों का बूलियन AND लेकर एक बूलियन फ़ॉर्मूला बनाते हैं। चरों का ऐसा असाइनमेंट होना जिसके परिणामस्वरूप बूलियन एक्सप्रेशन का परिणाम सत्य (true) हो, ऑस्ट्रेलिया के वैध 3-कलरिंग होने के समतुल्य है।

दूसरे शब्दों में, यदि हम ऑस्ट्रेलिया के लिए एक वैध 3-कलरिंग जानते हैं, तो हम ऊपर बनाए गए बूलियन फ़ॉर्मूले का एक असाइनमेंट भी जानते हैं।

बूलियन फ़ॉर्मूला पॉलीनोमियल टाइम में बनाया जाने योग्य होना चाहिए

हमें 3-कलरिंग के लिए इस बूलियन फ़ॉर्मूले को बनाने के लिए केवल पॉलीनोमियल संख्या में कदम (steps) उठाने की आवश्यकता है। विशेष रूप से, हमें आवश्यकता है:

प्रति क्षेत्र 3 कलर कंस्ट्रेंट्स
प्रति क्षेत्र अधिकतम N पड़ोसी कलर कंस्ट्रेंट्स

यह एक आवश्यकता है कि बूलियन फ़ॉर्मूला बनाने के लिए उठाए गए कदम पॉलीनोमियल टाइम में किए जाएं। यदि इसमें एक्सपोनेंशियल संख्या में कदम लगते हैं, तो बूलियन फ़ॉर्मूला एक्सपोनेंशियली बड़ा होगा, और witness एक्सपोनेंशियली बड़ा होगा — और पॉलीनोमियल टाइम में वेरीफाई नहीं किया जा सकेगा।

समस्याओं और प्रस्तावित समाधानों को मॉडल करने के लिए बूलियन अभिव्यक्तियों का उपयोग करने का सारांश

P और NP की सभी समस्याओं को एक बूलियन फ़ॉर्मूले के रूप में व्यक्त किया जा सकता है जो true आउटपुट देता है यदि हम संबंधित चर असाइनमेंट (witness) को जानते हैं, जो मूल समस्या के सही समाधान को एन्कोड करता है।

अब जब हमारे पास किसी समस्या के समाधान को कुशलतापूर्वक प्रदर्शित करने के लिए एक मानक भाषा है, तो हम एक समस्या का समाधान होने का प्रदर्शन करने के लिए एक मानक विधि के एक कदम करीब हैं — समाधान का खुलासा किए बिना, यानी, ज़ीरो नॉलेज प्रूफ्स (Zero Knowledge Proofs)।

भाग 3: P vs NP और ZK प्रूफ्स

P = NP का ZK प्रूफ्स से क्या संबंध है

ज़ीरो नॉलेज प्रूफ्स में “नॉलेज” (knowledge) का तात्पर्य witness के ज्ञान से है।

ZK प्रूफ्स कंप्यूटेशन के सत्यापन पहलू (verification aspect) से संबंधित हैं। यानी, यह देखते हुए कि आपको एक सुडोकू समाधान या मानचित्र का 3-कलरिंग मिल गया है, क्या आप किसी को ऐसा प्रमाण (witness) दे सकते हैं जो उन्हें कुशलता से यह वेरीफाई करने की अनुमति दे कि आपका समाधान सही है?

ZK प्रूफ्स यह प्रदर्शित करने का प्रयास करते हैं कि आप witness को उसे प्रकट किए बिना जानते हैं।

ZKPs केवल P या NP समस्याओं के साथ काम करते हैं। वे उन समस्याओं के लिए प्रयोग करने योग्य नहीं हैं जिन्हें हम कुशलता से वेरीफाई नहीं कर सकते।

यदि हमारे पास कुशलता से यह साबित करने का कोई तंत्र नहीं है कि रेगेक्स समतुल्य हैं, या शतरंज में एक निश्चित चाल इष्टतम है, तो ZK प्रूफ्स जादुई रूप से हमें ऐसा कुशल प्रमाण प्रस्तुत करने में सक्षम नहीं बना सकते हैं।

P और NP दोनों समस्याओं के लिए, समाधान का सत्यापन कुशलता से किया जा सकता है। ZK कंप्यूटेशन के विवरण को छुपाते हुए समाधान के वैध होने की पुष्टि करने में सक्षम बनाता है। इसके अलावा, ZK आपको सुडोकू पहेली का समाधान खोजने या मानचित्र की 3-कलरिंग खोजने में मदद नहीं कर सकता है। हालाँकि, यदि आपने इसे पहले ही कंप्यूट कर लिया है तो यह आपको किसी अन्य पार्टी को यह साबित करने में मदद कर सकता है कि आपके पास समाधान है।

P vs NP और ज़ीरो नॉलेज प्रूफ्स के बीच संबंध

वे सभी समस्याएँ जिनके समाधान तेज़ी से वेरीफाई किए जा सकते हैं, उन्हें बूलियन फ़ॉर्मूले में बदला जा सकता है।

किसी भी समस्या को बूलियन फ़ॉर्मूले में बदलने में सक्षम होना उत्तर को कुशलता से खोजने के लिए कोई चीट कोड (cheat code) नहीं है। एक मनमाने बूलियन अभिव्यक्ति को हल करना एक NP समस्या है, और इसका समाधान खोजना कठिन हो सकता है।

बूलियन फ़ॉर्मूले का आकार महत्वपूर्ण है। हमारे शतरंज के उदाहरण पर वापस जाते हुए, यदि आप हर स्थिति को बूलियन फ़ॉर्मूले के साथ मॉडल करने का प्रयास करते हैं, तो आपके फ़ॉर्मूले का आकार एक्सपोनेंशियली बड़ा होगा। इसलिए, केवल संभव समस्याएँ NP या P हैं, जिनके पास उचित आकार के बूलियन फ़ार्मुलें हैं जो उन्हें मॉडल करते हैं।

ZK साहित्य में, हम अक्सर बूलियन फ़ार्मुलों को बूलियन सर्किट (Boolean circuits) के रूप में संदर्भित करते हैं।

किसी समस्या के लिए ज़ीरो नॉलेज प्रूफ बनाना समस्या को सर्किट में अनुवाद करने पर आकर टिकता है, जैसा कि ऑस्ट्रेलिया के लिए थ्री-कलरिंग साबित करते समय या सॉर्ट की गई सूची को मान्य करते समय प्रदर्शित किया गया था। फिर, आप साबित करते हैं कि आपके पास सर्किट (witness) के लिए वैध इनपुट है, जो अंततः ज़ीरो नॉलेज प्रूफ में बदल जाता है।

किसी समस्या के समाधान को कुशलतापूर्वक वेरीफाई करने की क्षमता एक ज़ीरो नॉलेज प्रूफ बनाने की पूर्वापेक्षा (prerequisite) है कि आपके पास समाधान है। समाधान को कुशलतापूर्वक मॉडल करने के लिए किसी को बूलियन सर्किट बनाने में सक्षम होना चाहिए। हालाँकि, इष्टतम शतरंज चालों को निर्धारित करने जैसी समस्याओं के लिए, जो PSPACE से संबंधित हैं, इस दृष्टिकोण के परिणामस्वरूप एक्सपोनेंशियली बड़े सर्किट होते हैं, जो उन्हें अव्यावहारिक (impractical) बनाते हैं।

निष्कर्ष में, ज़ीरो नॉलेज प्रूफ्स केवल P और NP के भीतर उन समस्याओं के लिए संभव हैं, जहाँ कुशल समाधान सत्यापन संभव है। कुशल सत्यापन के बिना, किसी समस्या के लिए ज़ीरो नॉलेज प्रूफ बनाना असंभव हो जाता है।

अधिक जानें

ज़ीरो नॉलेज प्रूफ्स के और विषयों के लिए कृपया RareSkills ZK Book देखें।

तकनीकी बातें (Technicalities)

इस लेख में कुछ अवधारणाओं को सरल बनाया गया है ताकि उन्हें पहली बार देखने वाले किसी व्यक्ति के लिए यथासंभव समझने योग्य बनाया जा सके। यहाँ प्रस्तुत जानकारी यह समझाने के लिए पर्याप्त है कि ZK प्रूफ्स क्या कर सकते हैं और क्या नहीं कर सकते। इस विषय को आगे बढ़ाने के इच्छुक लोगों के लिए, यहाँ कुछ स्पष्टीकरण दिए गए हैं:

एक निश्चित आकार $(8 \times 8)$ के शतरंज बोर्ड को कठिनाई स्तर नहीं सौंपा जा सकता क्योंकि समस्या की कठिनाई को $\mathcal{O}(f(n))$ के रूप में व्यक्त नहीं किया जा सकता है। तकनीकी रूप से, हम कहते हैं कि मनमाने आकार का शतरंज PSPACE है। $10 \times 10$ शतरंज बोर्ड के बारे में सोचना भ्रमित करने वाला हो सकता है, लेकिन कोई केवल यह निर्दिष्ट (specify) कर सकता है कि अतिरिक्त स्थानों में शुरुआती स्थिति में कोई मोहरा नहीं है।
शतरंज का एक कम ज्ञात नियम है कि यदि कोई मोहरा नहीं मारा गया है और पिछले 50 चालों से कोई प्यादा नहीं चला है, तो खिलाड़ी ड्रा (draw) कह सकता है। यह खोज स्थान (search space) पर एक सीमा रखता है जो इसे PSPACE में डालता है। यदि इस नियम को हटा दिया जाता है, तो शतरंज का यह संस्करण EXPSPACE में है — समस्याओं की एक श्रेणी जिसके कंप्यूटेशन के लिए एक्सपोनेंशियल टाइम और एक्सपोनेंशियल मेमोरी आकार की आवश्यकता होती है।
कुछ NP समस्याओं को सब-एक्सपोनेंशियल टाइम (sub-exponential time) में हल किया जा सकता है, लेकिन व्यावहारिक उद्देश्यों के लिए, उन्हें हल करने में एक्सपोनेंशियल टाइम लगता है। उदाहरण के लिए $\mathcal{O}(2^{\sqrt{n}})$ तकनीकी रूप से सब-एक्सपोनेंशियल है, लेकिन यह अभी भी एक्सपोनेंशियली कठिन है।
कुछ NP समस्याओं के समाधान खोजने के लिए बहुत शक्तिशाली हि्यूरिस्टिक्स (heuristics) मौजूद हैं। यद्यपि थ्री कलरिंग को हल करने में एक्सपोनेंशियल टाइम लगता है, उचित आकार की समस्या के कई उदाहरणों को जल्दी से हल किया जा सकता है। उदाहरण के लिए, here are benchmark problems of maps with 200 territories and valid 3 colorings। चतुर एल्गोरिदम एक्सपोनेंशियली बड़े खोज स्थान की खोज किए बिना समाधान खोजने में सक्षम हैं। हालाँकि, NP समस्या को हल करने में तेज़ी लाने के लिए डिज़ाइन किए गए किसी भी हि्यूरिस्टिक्स के लिए, समस्या का एक पैथोलॉजिकल इंस्टेंस (pathological instance) बनाना संभव है जिसे हि्यूरिस्टिक का शोषण करने और इसे बेकार बनाने के लिए डिज़ाइन किया गया हो। फिर भी, समस्या के यथार्थवादी उदाहरण के विशिष्ट मामले के लिए हि्यूरिस्टिक्स अच्छी तरह से काम करते हैं।

मूल रूप से 10 अप्रैल, 2024 को प्रकाशित

Last updated on Aug 29, 2024

ज़ीरो नॉलेज प्रूफ्स को P vs NP समस्या से जोड़कर “समझना” बहुत आसान है।

इस ट्यूटोरियल के तीन भाग हैं:

P vs NP समस्या की व्याख्या
समस्याओं और समाधानों को एक बूलियन फ़ॉर्मूले (Boolean formula) के रूप में व्यक्त करना
P vs NP और वे ज़ीरो नॉलेज प्रूफ्स से कैसे संबंधित हैं

पूर्वापेक्षाएँ (Prerequisites)

भाग 1: P vs NP समस्या की व्याख्या

P में वे समस्याएँ होती हैं जिन्हें हल करना और जिनके समाधानों को वेरीफाई करना दोनों आसान होता है।

P उदाहरण 1: सूची (list) को सॉर्ट करना

हल करना (Solving): सूची को सॉर्ट करने में $\mathcal{O}(n \log n)$ टाइम लगता है (उदाहरण के लिए, mergesort का उपयोग करके), जो कि पॉलीनोमियल टाइम है। हालाँकि $n \log n$ एक पॉलीनोमियल नहीं है, लेकिन हम जानते हैं कि $\log n < n$ और इसलिए $(n \log n) < n²$ , इसलिए हमारे एल्गोरिदम का रनिंग टाइम किसी पॉलीनोमियल द्वारा ऊपर से सीमित (bounded) है, जो “पॉलीनोमियल टाइम” की आवश्यकता है।
वेरीफाई करना (Verifying): हम सूची को ट्रैवर्स (traverse) करके और यह जाँच कर कि प्रत्येक आइटम अपने बाएँ पड़ोसी से बड़ा है, यह वेरीफाई कर सकते हैं कि सूची सॉर्ट की गई है, जिसमें $\mathcal{O}(n)$ टाइम लगेगा।

P उदाहरण 2: सूची में किसी संख्या का इंडेक्स (index) वापस करना, यदि वह सूची में मौजूद है

हल करना (Solving): उदाहरण के लिए, दी गई सूची [8, 2, 1, 6, 7, 3] के लिए, हमें यह निर्धारित करने के लिए $\mathcal{O}(n)$ टाइम चाहिए कि क्या संख्या 7 सूची में है।
वेरीफाई करना (Verifying): लेकिन यदि हम आपको सूची देते हैं और कहते हैं कि 7 इंडेक्स 4 पर है, तो आप $\mathcal{O}(1)$ टाइम में वेरीफाई कर सकते हैं कि संख्या उस स्थिति में सूची में है। यदि हमें आइटम का स्थान नहीं बताया जाता है, तो किसी आइटम को खोजने में सामान्य स्थिति में $\mathcal{O}(n)$ टाइम लगता है क्योंकि हमें सूची में खोजना पड़ता है। यदि हमें आइटम का अनुमानित स्थान बताया जाता है, तो यह वेरीफाई करने में $\mathcal{O}(1)$ टाइम लगता है कि आइटम वास्तव में उस स्थान पर सूची में है।

P उदाहरण 3: यह निर्धारित करना कि ग्राफ में दो नोड्स जुड़े हुए हैं या नहीं

हल करना (Solving): ब्रेड्थ-फर्स्ट सर्च का उपयोग करके नोड्स के बीच का रास्ता खोजने में $\mathcal{O}(n + e)$ टाइम लगेगा, जहाँ $n$ ग्राफ में नोड्स की संख्या है और $e$ किनारों (edges) की संख्या है। किनारों की संख्या $e$ , $n^2$ से अधिक नहीं हो सकती है, इसलिए हम सबसे खराब स्थिति (worst case) में $\mathcal{O}(n + e)$ को $\mathcal{O}(n²)$ मान सकते हैं।
वेरीफाई करना (Verifying): हम केवल प्रस्तावित रास्ते का अनुसरण करके यह देखने के लिए कि क्या वे दो बिंदु वास्तव में उस रास्ते से जुड़े हुए हैं, $\mathcal{O}(n)$ टाइम में प्रस्तावित रास्ते के वैध होने की पुष्टि कर सकते हैं।

द विटनेस (The Witness)

सॉर्ट की गई सूची
वह इंडेक्स जहाँ सूची में संख्या दिखाई देती है
ग्राफ में दो नोड्स के बीच का रास्ता

PSPACE में समस्याएँ: सभी समस्याओं के समाधान ऐसे नहीं होते जिन्हें कुशलता से वेरीफाई किया जा सके

PSPACE में समस्याओं के उदाहरण

PSPACE उदाहरण 1: शतरंज (Chess) की इष्टतम (optimal) चाल खोजना

कंप्यूटर उत्तर देता है “काले प्यादे (pawn) को f4 से f3 पर ले जाएँ।”

आप कैसे भरोसा कर सकते हैं कि कंप्यूटर आपको सही उत्तर दे रहा है?

PSPACE उदाहरण 2: यह निर्धारित करना कि क्या रेगेक्स (regular expressions) समतुल्य (equivalent) हैं

PSPACE से भी अधिक कम्प्यूटेशनल रूप से गहन समस्याएँ

NP में समस्याएँ: कुछ समस्याओं को जल्दी से वेरीफाई किया जा सकता है लेकिन जल्दी से कंप्यूट नहीं किया जा सकता

NP में समस्याओं के उदाहरण। इन्हें नीचे अधिक विस्तार से समझाया गया है:

सुडोकू (Sudoku) पहेली के समाधान की गणना करना — सुडोकू पहेली के प्रस्तावित समाधान को वेरीफाई करना।
मानचित्र की 3-कलरिंग (3-coloring) की गणना करना (यदि यह मौजूद है) — मानचित्र की प्रस्तावित 3-कलरिंग को वेरीफाई करना।
बूलियन फ़ॉर्मूले (Boolean formula) के लिए एक असाइनमेंट खोजना जिसका परिणाम ‘true’ (सत्य) हो — यह वेरीफाई करना कि प्रस्तावित असाइनमेंट फ़ॉर्मूले का परिणाम ‘true’ देता है।

NP में समस्याओं के उदाहरण

NP उदाहरण 1: सुडोकू (Sudoku)

NP उदाहरण 2: मानचित्र की थ्री-कलरिंग (Three-coloring)

यह पता चलता है कि संयुक्त राज्य अमेरिका को 3-कलर करना संभव नहीं है।

हालाँकि, ऑस्ट्रेलिया को 3-कलर करना संभव है:

P, NP, और PSPACE के बीच संबंध

प्रत्येक वर्ग (class) के लिए कम्प्यूटेशनल संसाधन

श्रेणी (Category)	कंप्यूट टाइम (Compute Time)	वेरिफिकेशन टाइम (Verification Time)
P	पॉलीनोमियल या बेहतर होना चाहिए	पॉलीनोमियल या बेहतर होना चाहिए
NP	कोई आवश्यकता नहीं	पॉलीनोमियल या बेहतर होना चाहिए
PSPACE	कोई आवश्यकता नहीं	कोई आवश्यकता नहीं

P, NP, और PSPACE के बीच कठिनाई का पदानुक्रम (Hierarchy of Difficulty)

P vs NP समस्या

भाग 2: समस्याओं और समाधानों को बूलियन फ़ॉर्मूले (Boolean formulas) के रूप में व्यक्त करना

एक बूलियन फ़ॉर्मूले (Boolean formula) के समाधान

out = (x₁ ∨ ¬x₂ ∨ ¬ x₃) ∧ (¬x₂ ∨ x₃ ∨ x₄) ∧ (x₁ ∨ x₃ ∨ ¬x₄) ∧ (¬x₂ ∨ ¬x₃∨ ¬x₄)

\begin{align*} x₁ = T \\ x₂ = F \\ x₃ = T \\ x₄ = F \end{align*}

समाधान को फ़ॉर्मूले में रखने पर यह प्राप्त होता है:

\begin{align*} x₁ &= T \\ x₂ &= F \\ x₃ &= T \\ x₄ &= F \\ out &= (x₁ ∨ ¬x₂ ∨ ¬ x₃) ∧ (¬x₂ ∨ x₃ ∨ x₄) ∧ (x₁ ∨ x₃ ∨ ¬x₄)∧ (¬x₂ ∨ ¬x₃∨ ¬x₄) \\ out &= (T ∨ ¬ F ∨ ¬ T) ∧ (¬ F ∨ T ∨ F) ∧ (T ∨ T ∨ ¬ F) ∧ (¬ F ∨ ¬ T ∨ ¬ F) \\ &= (T) ∧ (T) ∧ (T) ∧ (T) \\ &= T \\ \end{align*}

P और NP की सभी समस्याओं को उन्हें बूलियन फ़ॉर्मूले में बदलकर और फ़ॉर्मूले का समाधान दिखाकर वेरीफाई किया जा सकता है

उदाहरण 1: बूलियन फ़ॉर्मूले का उपयोग करके जाँचना कि क्या कोई सूची सॉर्ट की गई है

A	B	A > B
0	0	0
0	1	0
1	0	1
1	1	0

अब एक ऐसी टेबल पर विचार करें जो $A = B$ व्यक्त करती है:

A	B	A = B
0	0	1
0	1	0
1	0	0
1	1	1

एक बिट नंबरों के लिए अभिव्यक्तियाँ (expressions):

\begin{align*} A > B &\rightarrow A ∧ ¬B \\ A = B &\rightarrow (A ∧ B) ∨ ¬(A ∨ B) \end{align*}

जल्द ही काम आएँगी।

अब हम एक बिट से अधिक के बाइनरी नंबरों की तुलना कैसे करें?

सबसे महत्वपूर्ण भिन्न बिट (most significant different bit) द्वारा बाइनरी तुलना

यदि $P = Q$ है, तो सभी बिट्स बराबर हैं। $P = Q$ का अर्थ है कि $P ≥ Q$ भी सत्य है:

यदि P < Q है, तो हम पहले बिट पर इसका पता लगा लेंगे जहाँ Q, 1 है और P, 0 है:

यदि $P ≥ Q$ तो निम्नलिखित में से एक सत्य होना चाहिए:

$p₄ > q₄$
$p₄ = q₄$ और $p₃ > q₃$
$p₄ = q₄$ और $p₃ = q₃$ और $p₂ > q₂$
$p₄ = q₄$ और $p₃ = q₃$ और $p₂ = q₂$ और $(p₁ > q₁ \text{ or } p₁ = q₁)$

हम बुलेट पॉइंट को एक एकल समीकरण में जोड़ सकते हैं।

\begin{align*} &((p₄ > q₄)) ∨ \\ &((p₄ = q₄) ∧ (p₃ > q₃)) ∨ \\ &((p₄ = q₄) ∧ (p₃ = q₃) ∧ (p₂ > q₂)) ∨ \\ &((p₄ = q₄) ∧ (p₃ = q₃) ∧ (p₂ = q₂) ∧ ((p₁ > q₁) ∨ (p₁ = q₁))) \end{align*}

\begin{align*} A > B &== A ∧ ¬B\\ A = B &== (A ∧ B) ∨ ¬(A ∨ B) \end{align*}

अंतिम बूलियन फ़ॉर्मूला जो 4 बिट्स के लिए $P ≥ Q$ व्यक्त करता है, वह है:

\begin{align*} &(p₄ ∧ ¬q₄) ∨ \\ &(((p₄ ∧ q₄) ∨ ¬(p₄ ∨ q₄)) ∧ (p₃ ∧ ¬q₃)) ∨ \\ &(((p₄ ∧ q₄) ∨ ¬(p₄ ∨ q₄)) ∧ ((p₃ ∧ q₃) ∨ ¬(p₃ ∨ q₃)) ∧ (p₂ ∧ ¬q₂)) ∨ \\ &(((p₄ ∧ q₄) ∨ ¬(p₄ ∨ q₄)) ∧ ((p₃ ∧ q₃) ∨ ¬(p₃ ∨ q₃)) ∧ ((p₂ ∧ q₂) ∨ ¬(p₂ ∨ q₂)) ∧ ((p₁ ∧ ¬q₁) ∨ ((p₁ ∧ q₁) ∨ ¬(p₁ ∨ q₁)))) \end{align*}

जाँचना कि क्या कोई सूची सॉर्ट की गई है

उदाहरण 2: बूलियन फ़ॉर्मूले के रूप में एक 3-कलरिंग

आइए एक बार फिर ऑस्ट्रेलिया के हमारे मानचित्र को देखें:

प्रत्येक क्षेत्र में तीन रंगों में से एक रंग है
प्रत्येक क्षेत्र का रंग उसके पड़ोसी से अलग है

(WA_G ∧ ¬WA_B ∧ ¬WA_R) ∨ (¬WA_G ∧ WA_B ∧ ¬WA_R) ∨ (¬WA_G ∧ ¬WA_B ∧ WA_R)

दूसरे शब्दों में:

"(West Australia हरा (green) है और West Australia नीला (blue) नहीं है और West Australia लाल (red) नहीं है)

या (OR)

(West Australia हरा (green) नहीं है और West Australia नीला (blue) है और West Australia लाल (red) नहीं है)

या (OR)

(West Australia हरा (green) नहीं है और West Australia नीला (blue) नहीं है और West Australia लाल (red) है)"

ज़ोर देने के लिए बूलियन फ़ॉर्मूले को रंगना:

(WA_G ∧ ¬WA_B ∧ ¬WA_R) ∨ (¬WA_G ∧ WA_B ∧ ¬WA_R) ∨ (¬WA_G ∧ ¬WA_B ∧ WA_R)

आइए उपरोक्त फ़ॉर्मूले को color assignment constraint कहें।

पड़ोसी रंग की बाधा (Neighboring color constraint)

¬(WA_G ∧ SA_G) ∧ ¬(WA_B ∧ SA_B) ∧ ¬(WA_R ∧ SA_R)

दूसरे शब्दों में:

यह ऐसा नहीं (NOT) है कि (West Australia हरा (green) है और South Australia हरा (green) है)

और (AND)

यह ऐसा नहीं (NOT) है कि (West Australia नीला (blue) है और South Australia नीला (blue) है)

और (AND)

यह ऐसा नहीं (NOT) है कि (West Australia लाल (red) है और South Australia लाल (red) है)"

ऑस्ट्रेलिया की 3-कलरिंग को मॉडल करने के लिए एक फ़ॉर्मूला

सबसे पहले, हम प्रत्येक क्षेत्र को एक चर नाम असाइन करते हैं:

WA = West Australia
SA = South Australia
NT = Northern Territory
Q = Queensland
NSW = New South Wales
V = Victoria

कलर कंस्ट्रेंट्स: छह क्षेत्रों में से प्रत्येक का ठीक एक रंग है:

(WA_G ∧ ¬WA_B ∧ ¬WA_R) ∨ (¬WA_G ∧ WA_B ∧ ¬WA_R) ∨ (¬WA_G ∧ ¬WA_B ∧ WA_R)
(SA_G ∧ ¬SA_B ∧ ¬SA_R) ∨ (¬SA_G ∧ SA_B ∧ ¬SA_R) ∨ (¬SA_G ∧ ¬SA_B ∧ SA_R)
(NT_G ∧ ¬NT_B ∧ ¬NT_R) ∨ (¬NT_G ∧ NT_B ∧ ¬NT_R) ∨ (¬NT_G ∧ ¬NT_B ∧ NT_R)
(Q_G ∧ ¬Q_B ∧ ¬Q_R) ∨ (¬Q_G ∧ Q_B ∧ ¬Q_R) ∨ (¬Q_G ∧ ¬Q_B ∧ Q_R)
(NSW_G ∧ ¬NSW_B ∧ ¬NSW_R) ∨ (¬NSW_G ∧ NSW_B ∧ ¬NSW_R) ∨ (¬NSW_G ∧ ¬NSW_B ∧ NSW_R)
(V_G ∧ ¬V_B ∧ ¬V_R) ∨ (¬V_G ∧ V_B ∧ ¬V_R) ∨ (¬V_G ∧ ¬V_B ∧ V_R)

बाउंड्री कंस्ट्रेंट्स: प्रत्येक पड़ोसी क्षेत्र एक रंग साझा नहीं करता है

Western Australia और South Australia:

¬(WA_G ∧ SA_G) ∧ ¬(WA_B ∧ SA_B) ∧ ¬(WA_R ∧ SA_R)

Western Australia और Northern Territory:

¬(WA_G ∧ NT_G) ∧ ¬(WA_B ∧ NT_B) ∧ ¬(WA_R ∧ NT_R)

Northern Territory और South Australia:

¬(NT_G ∧ SA_G) ∧ ¬(NT_B ∧ SA_B) ∧ ¬(NT_R ∧ SA_R)

Northern Territory और Queensland:

¬(NT_G ∧ Q_G) ∧ ¬(NT_B ∧ Q_B) ∧ ¬(NT_R ∧ Q_R)

South Australia और Queensland:

¬(SA_G ∧ Q_G) ∧ ¬(SA_B ∧ Q_B) ∧ ¬(SA_R ∧ Q_R)

South Australia और New South Wales:

¬(SA_G ∧ NSW_G) ∧ ¬(SA_B ∧ NSW_B) ∧ ¬(SA_R ∧ NSW_R)

South Australia और Victoria:

¬(SA_G ∧ V_G) ∧ ¬(SA_B ∧ V_B) ∧ ¬(SA_R ∧ V_R)

Queensland और New South Wales:

¬(Q_G ∧ NSW_G) ∧ ¬(Q_B ∧ NSW_B) ∧ ¬(Q_R ∧ NSW_R)

New South Wales और Victoria:

¬(NSW_G ∧ V_G) ∧ ¬(NSW_B ∧ V_B) ∧ ¬(NSW_R ∧ V_R)

बूलियन फ़ॉर्मूला पॉलीनोमियल टाइम में बनाया जाने योग्य होना चाहिए

प्रति क्षेत्र 3 कलर कंस्ट्रेंट्स
प्रति क्षेत्र अधिकतम N पड़ोसी कलर कंस्ट्रेंट्स

समस्याओं और प्रस्तावित समाधानों को मॉडल करने के लिए बूलियन अभिव्यक्तियों का उपयोग करने का सारांश

भाग 3: P vs NP और ZK प्रूफ्स

P = NP का ZK प्रूफ्स से क्या संबंध है

ज़ीरो नॉलेज प्रूफ्स में “नॉलेज” (knowledge) का तात्पर्य witness के ज्ञान से है।

ZKPs केवल P या NP समस्याओं के साथ काम करते हैं। वे उन समस्याओं के लिए प्रयोग करने योग्य नहीं हैं जिन्हें हम कुशलता से वेरीफाई नहीं कर सकते।

P vs NP और ज़ीरो नॉलेज प्रूफ्स के बीच संबंध

अधिक जानें

ज़ीरो नॉलेज प्रूफ्स के और विषयों के लिए कृपया RareSkills ZK Book देखें।

तकनीकी बातें (Technicalities)

एक निश्चित आकार $(8 \times 8)$ के शतरंज बोर्ड को कठिनाई स्तर नहीं सौंपा जा सकता क्योंकि समस्या की कठिनाई को $\mathcal{O}(f(n))$ के रूप में व्यक्त नहीं किया जा सकता है। तकनीकी रूप से, हम कहते हैं कि मनमाने आकार का शतरंज PSPACE है। $10 \times 10$ शतरंज बोर्ड के बारे में सोचना भ्रमित करने वाला हो सकता है, लेकिन कोई केवल यह निर्दिष्ट (specify) कर सकता है कि अतिरिक्त स्थानों में शुरुआती स्थिति में कोई मोहरा नहीं है।
शतरंज का एक कम ज्ञात नियम है कि यदि कोई मोहरा नहीं मारा गया है और पिछले 50 चालों से कोई प्यादा नहीं चला है, तो खिलाड़ी ड्रा (draw) कह सकता है। यह खोज स्थान (search space) पर एक सीमा रखता है जो इसे PSPACE में डालता है। यदि इस नियम को हटा दिया जाता है, तो शतरंज का यह संस्करण EXPSPACE में है — समस्याओं की एक श्रेणी जिसके कंप्यूटेशन के लिए एक्सपोनेंशियल टाइम और एक्सपोनेंशियल मेमोरी आकार की आवश्यकता होती है।
कुछ NP समस्याओं को सब-एक्सपोनेंशियल टाइम (sub-exponential time) में हल किया जा सकता है, लेकिन व्यावहारिक उद्देश्यों के लिए, उन्हें हल करने में एक्सपोनेंशियल टाइम लगता है। उदाहरण के लिए $\mathcal{O}(2^{\sqrt{n}})$ तकनीकी रूप से सब-एक्सपोनेंशियल है, लेकिन यह अभी भी एक्सपोनेंशियली कठिन है।
कुछ NP समस्याओं के समाधान खोजने के लिए बहुत शक्तिशाली हि्यूरिस्टिक्स (heuristics) मौजूद हैं। यद्यपि थ्री कलरिंग को हल करने में एक्सपोनेंशियल टाइम लगता है, उचित आकार की समस्या के कई उदाहरणों को जल्दी से हल किया जा सकता है। उदाहरण के लिए, here are benchmark problems of maps with 200 territories and valid 3 colorings। चतुर एल्गोरिदम एक्सपोनेंशियली बड़े खोज स्थान की खोज किए बिना समाधान खोजने में सक्षम हैं। हालाँकि, NP समस्या को हल करने में तेज़ी लाने के लिए डिज़ाइन किए गए किसी भी हि्यूरिस्टिक्स के लिए, समस्या का एक पैथोलॉजिकल इंस्टेंस (pathological instance) बनाना संभव है जिसे हि्यूरिस्टिक का शोषण करने और इसे बेकार बनाने के लिए डिज़ाइन किया गया हो। फिर भी, समस्या के यथार्थवादी उदाहरण के विशिष्ट मामले के लिए हि्यूरिस्टिक्स अच्छी तरह से काम करते हैं।

मूल रूप से 10 अप्रैल, 2024 को प्रकाशित