💻 computer science

Hardness of Range Avoidance and Proof Complexity Generators from Demi-Bits

यह शोध पत्र यह स्थापित करता है कि डेमी-बिट जनरेटरों (demi-bit generators) का अस्तित्व नॉन-डिटरमिनिस्टिक एल्गोरिदम के लिए रेंज अवॉयडेंस (Range Avoidance) समस्या की कठिनाई और कूक के सिद्धांत $\mathsf{PV}_1$ में ड्यूल वीक पिजनहोल सिद्धांत (dual weak pigeonhole principle) की अप्रमाणिकता को निहित करता है, साथ ही लगभग इष्टतम मापदंडों के साथ स्यूडो-सरजेक्टिव प्रूफ कॉम्प्लेक्सिटी जनरेटरों (pseudo-surjective proof complexity generators) के सरलीकृत निर्माण भी प्रदान करता है।

मूल लेखक: Hanlin Ren, Yichuan Wang, Yan Zhong

प्रकाशित 2026-03-16

📖 6 मिनट में पढ़ें🧠 गहराई से पढ़ें

CC BY 4.0

मूल लेखक: Hanlin Ren, Yichuan Wang, Yan Zhong

मूल पेपर CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/) के तहत लाइसेंस किया गया है। ✨ नीचे दिए गए पेपर की यह व्याख्या AI से तैयार की गई है। इसे लेखकों ने न तो लिखा है, न इसका समर्थन किया है। तकनीकी सटीकता के लिए मूल पेपर देखें। पूरा डिस्क्लेमर पढ़ें

बड़ी तस्वीर: "असंभव" पहेली

कल्पना कीजिए कि आपके पास एक मशीन (एक सर्किट) है जो एक छोटी चाबी (मान लीजिए 100 बिट्स) लेता है और उसे एक बहुत बड़े कोड (मान लीजिए 1,000 बिट्स) में बदल देता है। क्योंकि इस मशीन के पास छोटी चाबी है लेकिन वह एक विशाल कोड बनाती है, इसलिए यह हर संभव 1,000-बिट कोड नहीं बना सकती। ऐसे खरबों कोड हैं जिन्हें यह मशीन बनाना ही नहीं कर सकती।

समस्या (रेंज अवॉयडेंस - Range Avoidance):
आपका काम एक ऐसा कोड ढूँढना है जिसे यह मशीन नहीं बना सकती।

आसान तरीका: यदि आपको यादृच्छिक रूप से (randomly) अनुमान लगाने की अनुमति है, तो आप लगभग निश्चित रूप से एक ऐसा कोड ढूँढ लेंगे जिसे मशीन ने नहीं बनाया। यह दीवार पर निशाना लगाने जैसा है; मशीन ने दीवार पर केवल एक छोटा सा बिंदु बनाया है, इसलिए आप लगभग निश्चित रूप से खाली जगह पर निशाना लगाएंगे।
कठिन तरीका: यदि आपको डिटरमिनिस्टिक (कोई अनुमान नहीं, केवल शुद्ध तर्क) या नॉन-डिटरमिनिस्टिक (एक साथ सभी संभावनाओं को आज़माना, जैसे कि एक सुपर-फास्ट पैरेलल कंप्यूटर) होना है, तो उस खाली स्थान को ढूँढना अविश्वसनीय रूप से कठिन हो जाता है।

यह पेपर पूछता है: क्या वास्तव में इन स्मार्ट कंप्यूटरों के लिए उस खाली स्थान को ढूँढना असंभव है?

लेखक कहते हैं: हाँ, यह असंभव है, बशर्ते कि क्रिप्टोग्राफी की दुनिया में एक विशिष्ट प्रकार का "जादुई चमत्कार" (जिसे डेमी-बिट - Demi-Bit कहा जाता है) मौजूद हो।

मुख्य अवधारणा 1: "डेमी-बिट" (जादुई ट्रिक)

पेपर को समझने के लिए, आपको डेमी-बिट जनरेटर को समझना होगा।

सामान्य स्यूडो-रैंडम जनरेटर: एक जादूगर की कल्पना करें जो ताश की गड्डी को फेंटता है। यदि आप ऊपर का कार्ड देखते हैं, तो वह रैंडम (यादृच्छिक) दिखता है। लेकिन यदि आपके पास एक सुपर-स्मार्ट जासूस (एक कंप्यूटर) है, तो वे अंततः ट्रिक को समझ सकते हैं और अगले कार्ड की भविष्यवाणी कर सकते हैं।
डेमी-बिट जनरेटर: यह एक सुपर-जादूगर है। भले ही जासूस को "जादू" (नॉन-डिटरमिनिज्म—एक साथ सभी संभावनाओं को आज़माना) का उपयोग करने की अनुमति हो, फिर भी वे अगले कार्ड की भविष्यवाणी नहीं कर सकते। कार्ड जासूस के लिए पूरी तरह से रैंडम दिखता है, भले ही इसे एक सरल नियम द्वारा बनाया गया हो।

पेपर की खोज:
लेखकों ने सिद्ध किया कि यदि यह "सुपर-जादूगर" (डेमी-बिट) मौजूद है, तो "असंभव पहेली" (रेंज अवॉयडेंस) स्मार्ट कंप्यूटरों के लिए वास्तव में हल करने योग्य नहीं है। यदि आप पहेली को हल कर सकते हैं, तो आप जादूगर की ट्रिक को उजागर कर देंगे, जिससे यह सिद्ध हो जाएगा कि डेमी-बिट वास्तव में जादुई नहीं था।

मुख्य अवधारणा 2: "प्रूफ कॉम्प्लेक्सिटी" (अदालत)

यह पेपर प्रूफ कॉम्प्लेक्सिटी (Proof Complexity) के बारे में भी बात करता है। एक अदालत की कल्पना करें जहाँ एक वकील (एक प्रूफ सिस्टम) किसी कथन को सत्य सिद्ध करने का प्रयास करता है।

कथन: "यह विशिष्ट कोड $y$ इस मशीन द्वारा नहीं बनाया गया है।"
लक्ष्य: वकील को एक ऐसा प्रमाण लिखना होगा जो इतना छोटा और विश्वसनीय हो कि न्यायाधीश उसे जल्दी से स्वीकार कर ले।

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

उपमा:
एक ऐसे ताले की कल्पना करें जो इतना जटिल है कि भले ही आप जानते हों कि चाबी फिट नहीं बैठती, फिर भी आप यह समझाने के लिए एक सरल वाक्य नहीं लिख सकते कि वह क्यों नहीं बैठती। आपको यह समझाने के लिए एक पूरी किताब की आवश्यकता होगी। पेपर दिखाता है कि यदि डेमी-बिट मौजूद है, तो ऐसे "अस्पष्ट" ताले मौजूद हैं।

मुख्य अवधारणा 3: "छात्र और शिक्षक" का खेल

पेपर गणितीय तर्क (math logic) के लिए यह क्यों महत्वपूर्ण है, यह समझाने के लिए एक खेल का उपयोग करता है।

खेल: एक छात्र (पहेली सुलझाने की कोशिश करने वाला कंप्यूटर) मदद के लिए एक शिक्षक (जो सब कुछ जानता है) से मदद मांगता है।
- छात्र एक कोड का अनुमान लगाता है।
- यदि वह कोड मशीन द्वारा बनाया गया था, तो शिक्षक कहता है, "नहीं, यहाँ वह चाबी है जिसने इसे बनाया था।"
- छात्र उस चाबी का उपयोग करके एक बेहतर अनुमान लगाता है।
- वे $k$ राउंड तक खेलते हैं।
परिणाम: पेपर सिद्ध करता है कि यदि डेमी-बिट मौजूद है, तो छात्र खेल में जीत नहीं सकता, चाहे वे कितने भी राउंड खेलें (जब तक कि राउंड सीमित हों)। शिक्षक के पास हमेशा एक जवाबी चाल होती है।

यह क्यों मायने रखता है?
यह बाउंडेड अरिथमेटिक (Bounded Arithmetic) (गणितीय तर्क की एक शाखा) से जुड़ता है।

PV1: एक तार्किक प्रणाली जो "मानक" कंप्यूटर तर्क का प्रतिनिधित्व करती है।
APC1: एक अधिक शक्तिशाली प्रणाली जिसमें "रैंडमाइज्ड" तर्क शामिल है।
ब्रेकथ्रू: लेखकों ने सिद्ध किया कि APC1, PV1 से स्पष्ट रूप से अधिक शक्तिशाली है। सरल शब्दों में: ऐसी चीजें हैं जिन्हें आप सिद्ध कर सकते हैं यदि आपको रैंडमनेस (यादृच्छिकता) का उपयोग करने की अनुमति है, लेकिन आप उन्हें सिद्ध नहीं कर सकते यदि आपको पूरी तरह से डिटरमिनिस्टिक होने के लिए मजबूर किया जाता है। इसने गणितीय तर्क में दशकों पुराने सवाल को सुलझा दिया है।

पेपर की तीन बड़ी जीत

सरल धारणाएँ: पिछले पेपरों को इन चीजों को सिद्ध करने के लिए "सुपर-मैजिक" (जैसे इंडिस्टिंग्विशेबिलिटी ऑब्फस्केशन) की आवश्यकता थी। यह पेपर कहता है: "हमें उस भारी जादू की आवश्यकता नहीं है। हमें केवल हल्के, अधिक बुनियादी 'डेमी-बिट' जादू की आवश्यकता है।" यह परिणाम को अधिक विश्वसनीय और ठोस बनाता है।
सरल सर्किट: उन्होंने दिखाया कि भले ही मशीन बहुत सरल हो (बुनियादी गणितीय संचालन जैसे XOR और AND से बनी हो), पहेली फिर भी कठिन है। यह केवल जटिल मशीनों के लिए कठिन नहीं है; यह सरल मशीनों के लिए भी कठिन है।
"बेस्ट-केस" सरप्राइज: आमतौर पर, कंप्यूटर विज्ञान में, हम "वर्स्ट-केस" (सबसे कठिन इनपुट) परिदृश्य की चिंता करते हैं। लेकिन इस पेपर में, वे दिखाते हैं कि सबसे अच्छा संभव इनपुट (ढूँढने के लिए सबसे आसान कोड) भी सिद्ध करने में कठिन है। यह कहने जैसा है कि: "दुनिया की सबसे आसान पहेली भी असंभव है यदि आप इन नियमों का पालन करते हैं।"

एक वाक्य में सारांश

यदि एक विशिष्ट प्रकार का क्रिप्टोग्राफिक "जादुई चमत्कार" (डेमी-बिट) मौजूद है, तो कंप्यूटर रैंडम नंबर जनरेटरों में "छेद" (holes) नहीं ढूँढ सकते, वे उन छेदों के अस्तित्व के लिए छोटे प्रमाण नहीं लिख सकते, और वे सर्वज्ञ शिक्षक के खिलाफ अनुमान लगाने वाले खेल में नहीं जीत सकते, जो यह सिद्ध करता है कि कुछ गणितीय सत्य मानक डिटरमिनिस्टिक तर्क की पहुँच से मौलिक रूप से परे हैं।

यहाँ हनलिन रेन, यिचुआन वांग और यान झोंग के शोध पत्र "Hardness of Range Avoidance and Proof Complexity Generators from Demi-Bits" का विस्तृत तकनीकी सारांश दिया गया है।

1. समस्या का विवरण (Problem Statement)

यह शोध पत्र सैद्धांतिक कंप्यूटर विज्ञान की दो परस्पर जुड़ी समस्याओं को संबोधित करता है:

रेंज अवॉयडेंस (Range Avoidance - Avoid): एक बूलियन सर्किट $G: \{0,1\}^n \to \{0,1\}^m$ (जहाँ $m > n$ ) दिया गया है, जिसका लक्ष्य एक स्ट्रिंग $y \in \{0,1\}^m$ खोजना है ताकि $y \notin \text{Range}(G)$ हो। हालाँकि एक साधारण रैंडमाइज्ड एल्गोरिदम मौजूद है (एक रैंडम स्ट्रिंग आउटपुट करना), लेकिन कुशल डिटरमिनिस्टिक या नॉन-डिटरमिनिस्टिक एल्गोरिदम का अस्तित्व एक प्रमुख खुला प्रश्न है। 'Avoid' को डिटरमिनिस्टिक रूप से हल करने का अर्थ है स्पष्ट निर्माण (explicit constructions) और सर्किट लोअर बाउंड्स में बड़ी सफलता।
प्रूफ कॉम्प्लेक्सिटी जनरेटर्स (Proof Complexity Generators): एक सर्किट $G$ एक प्रूफ सिस्टम $P$ के विरुद्ध प्रूफ कॉम्प्लेक्सिटी जनरेटर है यदि कथन " $y \notin \text{Range}(G)$ " के लिए प्रत्येक $y$ हेतु $P$ में सुपर-पॉलीनोमियल प्रमाणों (super-polynomial proofs) की आवश्यकता होती है। यह कम्प्यूटेशनल हार्डनेस को औपचारिक प्रणालियों (formal systems) में कथनों की अप्रमाणनीयता (unprovability) से जोड़ता है।

लेखक "क्रिप्टोमानिया" (जैसे Indistinguishability Obfuscation) से "मिनीक्रिप्ट" (जैसे One-Way Functions/Pseudorandom Generators) जैसे कमजोर क्रिप्टोग्राफिक धारणाओं की ओर बढ़ते हुए, नॉन-डिटरमिनिस्टिक एडवर्सरीज के विरुद्ध 'Avoid' की हार्डनेस और प्रूफ कॉम्प्लेक्सिटी जनरेटर्स के अस्तित्व को स्थापित करने का लक्ष्य रखते हैं।

2. मुख्य कार्यप्रणाली (Core Methodology)

इस शोध पत्र का केंद्रीय नवाचार डेमी-बिट्स जनरेटर्स (Demi-Bits Generators) का उपयोग है, जो रुडिच (1997) द्वारा पेश किया गया एक प्रिमिटिव है।

डेमी-बिट्स (Demi-Bits): एक फलन $G: \{0,1\}^n \to \{0,1\}^m$ एक डेमी-बिट्स जनरेटर है यदि कोई नॉन-डिटरमिनिस्टिक एडवर्सरी (विशेष रूप से $\text{NP/poly}$ या $\text{AM}$ में) $G$ के आउटपुट को वास्तव में रैंडम स्ट्रिंग से गैर-नगण्य लाभ (non-negligible advantage) के साथ अलग नहीं कर सकता, भले ही एडवर्सरी रेंज में सदस्यता (membership) को सत्यापित कर सके।
एक्सट्रैक्शन तकनीक (Extraction Technique): लेखक एक डेमी-बिट्स जनरेटर को 'रेंज अवॉयडेंस' के लिए एक कठिन उदाहरण में बदलने के लिए रैंडमनेस एक्सट्रैक्टर्स (विशेष रूप से पेयरवाइज इंडिपेंडेंट हैश फंक्शन्स) का उपयोग करते हैं।
- वे एक नया सर्किट $C_r(s) = \text{Ext}(G(s), r)$ का निर्माण करते हैं, जहाँ $\text{Ext}$ एक स्ट्रॉन्ग सीडेड एक्सट्रैक्टर है और $r$ एक रैंडम सीड है।
- वे सिद्ध करते हैं कि यदि एक नॉन-डिटरमिनिस्टिक एल्गोरिदम $C_r$ के लिए 'Avoid' को हल कर सकता है, तो इसका उपयोग एक ऐसा नॉन-डिटरमिनिस्टिक एडवर्सरी बनाने के लिए किया जा सकता है जो अंतर्निहित डेमी-बिट्स जनरेटर की सुरक्षा को तोड़ सके।
स्टूडेंट-टीचर गेम्स (Student-Teacher Games): बाउंडेड अरिथमेटिक और प्रूफ कॉम्प्लेक्सिटी में परिणाम सिद्ध करने के लिए, लेखक स्टूडेंट-टीचर गेम फ्रेमवर्क का उपयोग करते हैं। एक "स्टूडेंट" (एल्गोरिदम) एक "टीचर" (जो विफल क्वेरीज़ के लिए प्री-इमेज प्रदान करता है) को खोजने की कोशिश करता है जो $G$ की रेंज के बाहर की स्ट्रिंग ढूंढ सके। इस गेम की हार्डनेस बाउंडेड अरिथमेटिक सिद्धांतों में रेंज अवॉयडेंस कथन की अप्रमाणनीयता के अनुरूप है।

3. मुख्य योगदान और परिणाम (Key Contributions and Results)

A. रेंज अवॉयडेंस की हार्डness (Avoid)

मुख्य प्रमेय (Theorem 1.1): पर्याप्त स्ट्रेच वाले डेमी-बिट्स जनरेटर्स (जैसे, $G: \{0,1\}^n \to \{0,1\}^{10n}$ $G : {0, 1}^{n} \to {0, 1}^{10 n}$ ) का अस्तित्व यह दर्शाता है कि Avoid $\notin$ SearchNP।
- महत्व: यह चेन और ली (STOC '24) द्वारा उठाए गए एक खुले प्रश्न को हल करता है। यह दिखाता है कि 'Avoid', पूर्ववर्ती कार्यों में उपयोग किए गए "क्रिप्टोमानिया" (iO, LWE) जैसी मजबूत धारणाओं के बजाय "मिनीक्रिप्ट-शैली" की धारणाओं (डेमी-बिट्स) के तहत नॉन-डिटरमिनिस्टिक एल्गोरिदम के लिए कठिन है।
- सरलीकरण: यह प्रमाण पिछले कार्यों की तुलना में काफी सरल है (आधे पृष्ठ में समाहित), जो मौलिक साइकोडो-रैंडम कंस्ट्रक्शंस और लेफ्टओवर हैश लेम्मा पर निर्भर करता है।
प्रतिबंधित सर्किट (Corollary 1.3): यह मानते हुए कि डेमी-बिट्स जनरेटर्स $\mathbb{F}_2$ पर कॉन्स्टेंट-डिग्री पॉलिनोमिअल्स द्वारा गणनीय हैं (जैसे, LPN या गोल्ड्रिच के PRG पर आधारित), रेंज अवॉयडेंस समस्या XOR $\circ$ AND $_d$ सर्किट्स (कॉन्स्टेंट-डिग्री पॉलिनोमिअल्स) के लिए कठिन बनी रहती है। यह हार्डनेस परिणामों को उन प्रतिबंधित सर्किट क्लासेज तक विस्तारित करता जो पहले अज्ञात थे।

B. प्रूफ कॉम्प्लेक्सिटी जनरेटर्स (Proof Complexity Generators)

रूपांतरण (Theorem 1.4): लेखक दिखाते हैं कि एक प्रूफ सिस्टम $P$ $P$ के विरुद्ध सुरक्षित डेमी-बिट्स जनरेटर्स को $P$ $P$ के विरुद्ध सुरक्षित प्रूफ कॉम्प्लेक्सिटी जनरेटर्स में बदला जा सकता है, बशर्ते $P$ $P$ "सिंपल पैरिटी रिडक्शन" के तहत बंद (closed) हो।
- यह प्रूफ कॉम्प्लेक्सिटी जनरेटर्स के निर्माण के लिए एक नया, मॉड्यूलर दृष्टिकोण प्रदान करता: आपको केवल विशिष्ट प्रूफ सिस्टम के विरुद्ध एक डेमी-बिट्स जनरेटर बनाना होगा।
स्यूडो-सरजक्टिविटी (Pseudo-Surjectivity) (Theorem 1.7): $\text{NP/poly}$ $NP/poly$ के विरुद्ध सुरक्षित डेमी-बिट्स जनरेटर्स की धारणा के तहत, लेखक ऐसे जनरेटर्स का निर्माण करते हैं जो $k$ -राउंड स्यूडो-सरजक्टिव हैं।
- स्यूडो-सरजक्टिविटी प्रूफ कॉम्प्लेक्सिटी जनरेटर्स के लिए सबसे मजबूत ज्ञात हार्डनेस धारणा है, जो यह दर्शाती है कि इंटरैक्टिव प्रोटोकॉल (स्टूडेंट-टीचर गेम्स) भी रेंज के बाहर की स्ट्रिंग को कुशलतापूर्वक नहीं खोज सकते।
- सीमा: पैरामीटर्स अभी तक ट्रुथ टेबल जनरेटर की स्यूडो-सरजक्टिविटी को सिद्ध करने के लिए आवश्यक क्षेत्र तक नहीं पहुँच पाए हैं, लेकिन इसे वर्तमान सामान्यता की एक अंतर्निहित सीमा के रूप में दिखाया गया है।

C. बाउंडेड अरिथमेटिक सिद्धांतों का पृथक्करण (Separation of Bounded Arithmetic Theories)

$\text{PV}_1$ और $\text{APC}_1$ का पृथक्करण (Theorem 1.5): यह शोध पत्र सिद्ध करता है कि कुक के सिद्धांत $\text{PV}_1$ $PV_{1}$ (डिटरमिनिस्टिक पॉलीटाइम रीजनिंग) में पॉलीटाइम फंक्शन्स के लिए ड्यूल वीक पिजनहोल प्रिंसिपल (dwPHP) अप्राप्य है, यह मानते हुए कि $\text{AM/O(1)}$ $AM/O(1)$ के विरुद्ध सुरक्षित डेमी-बिट्स जनरेटर्स मौजूद हैं।
- यह दर्शाता है कि जेरेबैक का सिद्धांत $\text{APC}_1$ (जिसमें dwPHP शामिल है) $\text{PV}_1$ का एक सख्त विस्तार है।
- पिछले पृथक्करण iO या कम संभावित धारणाओं पर निर्भर थे; यह परिणाम एक अधिक स्वाभाविक क्रिप्टोग्राफिक प्रिमिटिव का उपयोग करता है जो नॉन-डिटरमिनिस्टिक एडवर्सरीज के विरुद्ध काम करता है।
राउंड कॉम्प्लेक्सिटी (Theorem 1.6): लेखक इसे $\text{AM/O(\log k)}$ के विरुद्ध डेमी-बिट्स को मानते हुए, $k$ राउंड में डिटरमिनिस्टिक पॉलीटाइम स्टूडेंट्स को स्टूडेंट-टीचर गेम जीतने से रोकने के लिए सामान्यीकृत करते हैं।

4. महत्व और प्रभाव (Significance and Impact)

धारणाओं को कमजोर करना (Weakening Assumptions): यह शोध पत्र सफलतापूर्वक रेंज अवॉयडेंस की हार्डनेस को "क्रिप्टोमानिया" (iO, सब-एक्सपोनेंशियल LWE) से "मिनीक्रिप्ट" (डेमी-बिट्स, संभावित रूप से LPN/PRGs पर आधारित) की ओर स्थानांतरित करता है। यह जटिलता पृथक्करणों को न्यूनतम क्रिप्टोग्राफिक धारणाओं पर आधारित करने की दिशा में एक महत्वपूर्ण कदम है।
वैचारिक स्पष्टता (Conceptual Clarity): डेमी-बिट्स + एक्सट्रैक्शन को अलग करके, लेखक हार्डनेस सिद्ध करने के लिए एक स्वच्छ, अधिक मॉड्यूलर फ्रेमवर्क प्रदान करते हैं। यह पिछले परिणामों के प्रमाणों को सरल बनाता है और सामान्यीकरण के द्वार खोलता है।
एवरेज-केस से बेस्ट-केस रिडक्शन (Average-Case to Best-Case Reduction): यह शोध पत्र प्रूफ कॉम्प्लेक्सिटी में एक अनूठी घटना को उजागर करता है: एक एवरेज-केस हार्डनेस धारणा (डेमी-बिट्स को औसतन पहचानना कठिन है) को बेस्ट-केस हार्डनेस परिणाम (प्रत्येक आउटपुट $y$ के लिए प्रूफ कॉम्प्लेक्सिटी जनरेटर्स कठिन हैं) में बदलना। यह "एवरेज-केस से बेस्ट-केस" रिडक्शन नॉन-डिटरमिनिस्टिक एडवर्सरीज और प्रूफ कॉम्प्लेक्सिटी के परिवेश में अद्वितीय है।
लोअर बाउंड्स के लिए नए दिशा-निर्देश: परिणाम मजबूत प्रूफ सिस्टम (जैसे $\text{Res}[\oplus]$ ) के लिए लोअर बाउंड्स सिद्ध करने का एक ठोस मार्ग सुझाते हैं: पहले उस सिस्टम के विरुद्ध एक डेमी-बिट्स जनरेटर का निर्माण करें, फिर रूपांतरण प्रमेय को लागू करें।

5. निष्कर्ष (Conclusion)

रेन, वांग और झोंग डेमी-बिट्स जनरेटर्स और रेंज अवॉयडेंस एवं प्रूफ कॉम्प्लेक्सिटी की हार्डनेस के बीच एक मौलिक संबंध स्थापित करते हैं। उनका कार्य यह प्रदर्शित करता है कि नॉन-डिटरमिनिस्टिक एडवर्सरीज के विरुद्ध इन क्रिप्टोग्राफिक प्रिमिटिव्स का अस्तित्व प्रमुख जटिलता वर्गों (SearchNP बनाम Avoid) को अलग करने, बाउंडेड अरिथमेटिक सिद्धांतों ( $\text{PV}_1$ बनाम $\text{APC}_1$ ) को अलग करने और मजबूत प्रूफ कॉम्प्लेक्सिटी जनरेटर्स के निर्माण के लिए पर्याप्त है। उनके परिणाम क्रिप्टोग्राफी, सर्किट कॉम्प्लेक्सिटी और प्रूफ कॉम्प्लेक्सिटी को जोड़ने वाले सैद्धांतिक आधारों के महत्वपूर्ण सरलीकरण और सुदृढ़ीकरण का प्रतिनिधित्व करते हैं।