💻 संगणक विज्ञान

Optimal Shallow Circuits for Majority

यह शोध पत्र किसी भी सममित फलन (symmetric function) के लिए आकार $2^{O(n^{1/(d-1)})}$ वाले गहराई- $d$ के सर्किटों का एक GPT-6 Astra-खोजा गया निर्माण प्रस्तुत करता है, जिससे मैजॉरिटी (Majority) की एसिम्प्टोटिक $\mathrm{AC}^0$ जटिलता को हॉस्टैड (Håstad) के लंबे समय से चले आ रहे निचले स्तर के बंधन (lower bound) से मेल खाकर हल किया गया है।

मूल लेखक: Victor Lecomte, Prasanna Ramakrishnan

प्रकाशित 2026-10-01

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

CC BY 4.0

मूल लेखक: Victor Lecomte, Prasanna Ramakrishnan

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

कंप्यूटर विज्ञान के विशाल परिदृश्य में, एक मौलिक प्रश्न है जिसने दशकों से शोधकर्ताओं को व्यस्त रखा है: किसी समस्या को हल करने में वास्तव में कितनी मेहनत लगती है? इसका उत्तर देने के लिए, वैज्ञानिक केवल सुपर कंप्यूटरों पर प्रोग्राम नहीं चलाते; वे गणना के सैद्धांतिक मॉडल बनाते हैं जिन्हें सर्किट कहा जाता है। एक सर्किट की कल्पना एक स्विच और लॉजिक गेट्स के विशाल, जटिल जाल के रूप में करें, जहाँ सूचना नीचे से ऊपर की ओर प्रवाहित होती है, और हर चरण पर संसाधित होती है। लक्ष्य यह देखना है कि इस वेब (जाल) को कितना छोटा और कितना उथला बनाया जा सकता है, जबकि वह अभी भी एक विशिष्ट कार्य को निष्पादित कर सके। यदि किसी कार्य के लिए एक ऐसा सर्किट आवश्यक है जो असंभव रूप से विशाल या अविश्वसनीय रूप से गहरा है, तो हम उस कार्य को स्वाभाविक रूप से कठिन मानते हैं। चालीस वर्षों तक, एक सरल कार्य कितना कठिन हो सकता है, इसकी सर्वोत्तम ज्ञात सीमा 'पैरिटी' (Parity) नामक एक फलन (function) द्वारा निर्धारित की गई थी, जो केवल यह जाँचता है कि संख्याओं की एक सूची में एकों (ones) की संख्या विषम है या सम। यह सीमा एक ऐसी दीवार के रूप में खड़ी थी जिसे कोई पार नहीं कर सका, यहाँ तक कि अन्य समान रूप से कठिन कार्यों के लिए भी।

इन अन्य कार्यों के बीच, 'मेजोरिटी' (Majority) फंक्शन शोधकर्ताओं का एक पसंदीदा लक्ष्य रहा है जो उस दीवार को तोड़ने की कोशिश कर रहे थे: मेजोरिटी फंक्शन। यह एकों और शून्यों की एक सूची लेता है और यदि इनपुट का आधे से अधिक हिस्सा एकों का है तो एक (one) आउटपुट देता है, अन्यथा शून्य (zero) देता है। यह सहज रूप से पैरिटी की तुलना में अधिक जटिल लगता है, और लंबे समय तक, मेजोरity के लिए जो सर्वोत्तम सर्किट कोई बना सकता था, वे सैद्धांतिक न्यूनतमों की तुलना में काफी बड़े थे। जो हम बना सकते थे और जो हमें लगता था कि आवश्यक है, उनके बीच का यह अंतर एक अनसुलझे रहस्य की तरह बना रहा। क्या मेजोरिटी फंक्शन वास्तव में पैरिटी से कठिन था, जिसके लिए बहुत बड़े सर्किट की आवश्यकता थी? या हमारी छोटे सर्किट बनाने में अक्षमता केवल इस बात का संकेत थी कि हम कोई चतुर युक्ति भूल रहे थे? दशकों तक, क्षेत्र इस उत्तर की प्रतीक्षा करता रहा, इस उम्मीद में कि इस विशिष्ट पहेली को सुलझाने से उन उपकरणों का मार्ग प्रशད་ मिलेगा जो और भी बड़ी, मौलिक समस्याओं को हल करने के लिए आवश्यक हैं।

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

इस खोज का मार्ग दृष्टिकोण में बदलाव के साथ शुरू हुआ। वर्षों तक, शोधकर्ताओं ने 'डिवाइड एंड कॉन्कर' (divide and conquer) नामक एक मानक रणनीति का उपयोग करके मेजोरिटी समस्या को हल करने का प्रयास किया। इस दृष्टिकोण में संख्याओं की एक बड़ी सूची को छोटे टुकड़ों में तोड़ना, प्रत्येक टुकड़े के लिए समस्या को हल करना और फिर परिणामों को संयोजित करना शामिल है। जबकि यह विधि कई समस्याओं के लिए अच्छी तरह काम करती है, इसने मेजोरिटी के लिए ऐसे सर्किट बनाए जो थोड़े अधिक बड़े थे, जिनमें जटिलता का एक अतिरिक्त कारक शामिल था जो अपरिहार्य प्रतीत होता था। नया कार्य सुझाव देता है कि इस समस्या के बारे में सोचने का पारंपरिक तरीका एकमात्र नहीं था। डेटा के छोटे टुकड़ों के परिणामों को सीधे संयोजित करने के बजाय, शोधकर्ताओं ने "परीक्षणों" (tests) की एक प्रणाली डिजाइन की।

इनपुट की कल्पना डेटा के ब्लॉकों के एक संग्रह के रूप में करें। नई विधि तुरंत एकों की कुल संख्या गिनने की कोशिश नहीं करती है। इसके बजाय, यह परीक्षणों की एक श्रृंखला स्थापित करती है जो सत्यापित करती है कि ब्लॉकों के पास एक-दूसरे के सापेक्ष विशिष्ट, भिन्न गुण हैं। शोधकर्ताओं ने इनपुट को कई ब्लॉकों में विभाजित किया और प्रत्येक ब्लॉक को एक रैंडम शिफ्ट (random shift) सौंपा। फिर उन्होंने जाँच की कि क्या ब्लॉकों के शिफ्ट किए गए मान एक-दूसरे से भिन्न हैं। यदि ब्लॉक सभी भिन्न थे, तो एक गणितीय गुण ने गारंटी दी कि मूल इनपुट का कुल योग एक विशिष्ट लक्ष्य संख्या से मेल खाएगा। इस जाँच को बहुत कुशलता से किया जा सकता था क्योंकि इसमें पूरे डेटासेट का विश्लेषण करने के बजाय केवल ब्लॉकों के जोड़ों की तुलना करने की आवश्यकता थी।

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

शोधकर्ताओं ने यह भी दिखाया कि यह विधि किसी भी 'सिमेट्रिक फंक्शन' (symmetric function) के लिए काम करती है, जो समस्याओं की एक विस्तृत श्रेणी है जहाँ उत्तर केवल एकों की कुल संख्या पर निर्भर करता है, न कि उनके विशिष्ट क्रम पर। इसमें मेजोरिटी शामिल है, लेकिन कई अन्य फलन भी। यह प्रमाण 'कलर-कोडिंग' (color-coding) नामक एक तकनीक पर निर्भर करता है, जो ग्राफ थ्योरी से लिया गया एक विचार है जिसमें विशिष्ट पैटर्न खोजने के लिए तत्वों को यादृच्छिक रूप से लेबल किया जाता है। इस संदर्भ में, रैंडम शिफ्ट 'रंगों' की तरह कार्य करते हैं, यह सुनिश्चित करते हुए कि ब्लॉक इस तरह से भिन्न हों कि वे कुल संख्या को प्रकट कर सकें। टीम ने इस निर्माण के लिए प्रारंभिक विचार उत्पन्न करने के लिए एक कृत्रिम बुद्धिमत्ता प्रणाली का उपयोग किया, लेकिन मानव शोधकर्ता इस बात को कठोरता से सिद्ध करने और यह समझाने के लिए जिम्मेदार थे कि विचार क्यों सही था।

यह परिणाम महत्वपूर्ण है क्योंकि यह सर्किट जटिलता के अध्ययन में एक प्रमुख बाधा को हटा देता है। लंबे समय तक, तथ्य यह कि मेजोरिटी को पैरिटी की तुलना में बड़े सर्किटों की आवश्यकता प्रतीत होती थी, यह दर्शाता था कि निचले स्तर के प्रमाण (lower bounds) देने वाले हमारे उपकरण अपूर्ण थे। यदि मेजोरिटी वास्तव में पैरिटी से अधिक कठिन थी, तो इसका अर्थ यह हो सकता था कि मौजूदा सीमाएँ सटीक नहीं थीं, और हमें गणना की कठिनाई को समझने के लिए नए, अधिक शक्तिशाली गणितीय उपकरणों की आवश्यकता थी। यह दिखाकर कि मेजोरिटी को वास्तव में छोटे सर्किट्स के साथ बनाया जा सकता है, यह पेपर पुष्टि करता है कि मौजूदा उपकरण पूरे समय पर्याप्त थे। यह सुझाव देता है कि इन सीमाओं को सुधारने की कठिनाई गणितीय शक्ति की कमी के कारण नहीं, बल्कि सर्किट बनाने के सही दृष्टिकोण की कमी के कारण थी।

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

अंत में, यह पेपर एक ऐसे प्रश्न का स्पष्ट और निर्णायक उत्तर प्रदान करता है जो दशकों से बना हुआ था। मेजोरिटी फंक्शन, जिसे कभी पैरिटी से अधिक कठिन माना जाता था, अब ज्ञात है कि वह जटिलता के उसी स्तर पर है। इसका निर्माण अपने तर्क में सरल है लेकिन इसके निहितार्थ गहरे हैं, यह दर्शाता है कि कभी-कभी सबसे कुशल समाधान प्रत्यक्ष गणना नहीं, बल्कि संभावनाओं को कवर करने वाले जाँचों की एक चतुर व्यवस्था है। यह खोज केवल एक विशिष्ट समस्या को हल नहीं करती है; यह अन्य जटिल कार्यों के लिए कुशल सर्किट बनाने के बारे में सोचने का एक नया तरीका प्रदान करती है। यह सुझाव देती है कि समस्याओं को प्रत्यक्ष गणना के बजाय रैंडम टेस्टिंग और पैटर्न मिलान के लेंस से देखकर, हम कंप्यूटर विज्ञान की अन्य दीर्घकालिक चुनौतियों के लिए अधिक कुशल समाधान पा सकते हैं। यह कार्य एक अनुस्मारक के रूप में खड़ा है कि गणना के अध्ययन में, कठिन समस्याओं को अक्सर बड़ी मशीनें बनाकर नहीं, बल्कि डेटा को देखने का एक सरल तरीका ढूंढकर हल किया जाता है।

तकनीकी सारांश: मेजॉरिटी (Majority) के लिए इष्टतम शैलो सर्किट्स (Shallow Circuits)

समस्या विवरण
चार दशकों से, कांस्टेंट-डेप्थ सर्किट्स ( $AC^0$ ) के भीतर मेजॉरिटी (Majority) फलन की एसिम्प्टोटिक सर्किट कॉम्प्लेक्सिटी (asymptotic circuit complexity) एक खुला प्रश्न बना हुआ था। जबकि हॉस्टैड (Hästad, 1986) के स्विचिंग लेम्मा ने पैरिटी (Parity) फलन के लिए $2^{\Omega(n^{1/(d-1)})}$ का लोअर बाउंड स्थापित किया था, मेजॉरिटी के लिए डेप्थ- $d$ सर्किट्स के लिए ज्ञात सर्वोत्तम अपर बाउंड में एक अतिरिक्त पॉिलॉगैरिथमिक (polylogarithmic) कारक शामिल था, जो विशेष रूप से $2^{O(n^{1/(d-1)} (\log n)^{1-1/(d-1)})}$ था। इस अंतर ने यह संकेत दिया कि मेजॉरिटी को पैरिटी की तुलना में काफी बड़े सर्किट्स की आवश्यकता हो सकती है, या मौजूदा लोअर बाउंड तकनीकें मेजॉरिटी के लिए अनुकूलता (optimality) सिद्ध करने के लिए अपर्याप्त थीं। यह विशिष्ट प्रश्न कि क्या मेजॉरिटी डेप्थ-3 सर्किट्स के आकार $2^{O(\sqrt{n})}$ (जो पैरिटी लोअर बाउंड के बराबर है) को स्वीकार करती है, हॉस्टैड, जुक्ना और पुडलाक (Hästad, Jukna, and Pudlák, 1993) द्वारा उठाया गया था।

कार्यप्रणाली (Methodology)
यह शोध पत्र किसी भी सिमेट्रिक फंक्शन (मेजॉरिटी सहित) के लिए डेप्थ- $d$ सर्किट्स का निर्माण प्रस्तुत करता है जो आकार $2^{O(n^{1/(d-1)})}$ की सीमा प्राप्त करता है। प्रमाण की रणनीति "टॉप-डाउन" (top-down) है, जो सर्किट को उन टेस्ट्स के OR के रूप में देखती है जो यह प्रमाणित करते हैं कि इनपुट का हैमिंग वेट (Hamming weight) एक विशिष्ट मान का है (डेप्थ-3 के लिए CNF और सामान्य डेप्थ के लिए $\Pi_{d-1}$ सर्किट)।

निर्माण दो मुख्य चरणों में आगे बढ़ता है:

कुशल टेस्ट्स (Tests) डिजाइन करना:
कैनोनिकल डिवाइड-एंड-कन्कर (divide-and-conquer) दृष्टिकोण के बजाय, जो प्रत्येक ब्लॉक के वेट की गणना करता है और उन्हें जोड़ता है, लेखक ऐसे "टेस्ट्स" डिजाइन करते हैं जो व्यक्तिगत ब्लॉक वेट को फिक्स किए बिना कुल वेट को $k$ के मॉड्यूल (modulo) में प्रमाणित करते हैं।
- इनपुट को $k$ ब्लॉक्स में विभाजित किया जाता है।
- प्रत्येक ब्लॉक $i$ के लिए, उसके हैमिंग वेट $w_i$ पर एक निश्चित शिफ्ट $s_i$ लागू किया जाता है।
- टेस्ट यह जांचता है कि क्या शिफ्ट किए गए वेट $w_1+s_1, \dots, w_k+s_k$ $k$ के मॉड्यूल में अलग-अलग (distinct) हैं।
- यदि वे अलग-अलग हैं, तो उनका योग $k$ के मॉड्यूल में $\binom{k}{2}$ के बराबर होता है। ऐसे शिफ्ट चुनने से कि $\sum s_i \equiv \binom{k}{2} - t \pmod k$ , टेस्ट यह प्रमाणित करता है कि कुल वेट $|x| \equiv t \pmod k$ है।
- कार्यान्वयन (Implementation): यह शर्त कि शिफ्ट किए गए वेट अलग-अलग हैं, पेयरवाइज तुलनाओं (pairwise comparisons) का एक AND है। प्रत्येक तुलना केवल दो ब्लॉक्स पर निर्भर करती है, जिससे यह एक "जंटा" (junta - कुछ चरों का फलन) बन जाता है।
  - डेप्थ-3 के लिए: इन तुलनाओं को छोटे CNFs के रूप में लागू किया जाता है।
  - डेप्थ- $d$ के लिए: लेखक देखते हैं कि तुलना फलन दो ब्लॉक्स के चरों के संबंध में सिमेट्रिक है (एक ब्लॉक के चरों को नेगेटिव मानकर), जो प्रत्येक तुलना को एक छोटे $\Pi_{d-1}$ सर्किट के रूप में लागू करने के लिए इंडक्टिव हाइपोथीसिस (inductive hypothesis) के उपयोग की अनुमति देता है।
- सटीक वेट $t$ (केवल मॉड्यूल $k$ के बजाय) को प्रमाणित करने के लिए, निर्माण चाइनीज रिमाइंडर थ्योरम (Chinese Remainder Theorem) का उपयोग करता है, जो $d-1$ सह-अभाज्य (pairwise coprime) मॉडुली $k_1, \dots, k_{d-1}$ पर टेस्ट्स को जोड़ता है, जिनमें से प्रत्येक लगभग $n^{1/(d-1)}$ है।
प्रोबेबिलिस्टिक कवरेज (Probabilistic Coverage):
लेखक दिखाते हैं कि यादृच्छिक रूप से निर्मित टेस्ट्स का एक छोटा संग्रह सभी वैध इनपुट्स को कवर करने के लिए पर्याप्त है।
- एक निश्चित वैध इनपुट $x$ (वेट $t$ के साथ) के लिए, एक रैंडम टेस्ट (रैंडम शिफ्ट के साथ जो सम CONSTRAINT को पूरा करता है) द्वारा $x$ को स्वीकार करने की प्रायिकता कम से कम $e^{-k}$ है (जो वैध शिफ्ट परम्यूटेशन $k!$ और कुल शिफ्ट विकल्पों $k^{k-1}$ के अनुपात से प्राप्त हुई है)।
- प्रोबेबिलिस्टिक मेथड द्वारा, $T \approx n/p$ रैंडम टेस्ट्स (जहाँ $p$ सफलता की प्रायिकता है) का चयन करना यह सुनिश्चित करता है कि सभी वैध इनपुट्स कवर हो जाएं।
- अंतिम सर्किट इन $T$ टेस्ट्स का OR है।

मुख्य योगदान और परिणाम

थ्योरम 1: किसी भी स्थिरांक $d \ge 2$ के लिए, $n$ वेरिएबल्स वाले प्रत्येक सिमेट्रिक फंक्शन के लिए डेप्थ- $d$ सर्किट्स का आकार $2^{O(n^{1/(d-1)})}$ होता है।
मेजॉरिटी गैप का समाधान: यह परिणाम पैरिटी के हॉस्टैड लोअर बाउंड से मेल खाता है, जिससे यह सिद्ध होता है कि मेजॉरिटी की एसिम्प्टोटिक सर्किट कॉम्प्लेक्सिटी पैरिटी के समान ही है। पहले से संदिग्ध अतिरिक्त पॉिलॉगैरिथमिक कारक वाला अपर बाउंड अनावश्यक था।
डेप्थ-3 केस: विशेष रूप से, यह पेपर सिद्ध करता है कि सिमेट्रिक फंक्शन्स के पास डेप्थ-3 सर्किट्स का आकार $2^{O(\sqrt{n})}$ होता है, जो हॉस्टैड, जुक्ना और पुडलाक (1993) द्वारा उठाए गए प्रश्न को हल करता है।
सामान्यीकरण (Generalization): यह निर्माण केवल मेजॉरिटी या पैरिटी ही नहीं, बल्कि किसी भी सिमेट्रिक फंक्शन पर लागू होता है।

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

पेपर दो विशिष्ट निहितार्थों पर प्रकाश डालता है:

हॉस्टैड के बाउंड की इष्टतमता (Optimality): स्विचिंग लेम्मा ने मेजॉरिटी के लिए सही एसिम्प्टोटिक बाउंड हमेशा से ही दिया था; इसे सिद्ध करने में कठिनाई एक मिलान योग्य अपर बाउंड निर्माण की कमी के कारण थी, न कि लोअर बाउंड तकनीक की सीमा के कारण।
कलर-कोडिंग (Color-Coding) से संबंध: ब्लॉक वेट्स को रैंडमली हैश करने और डिस्टिंक्टनेस (distinctness) के लिए टेस्ट करने की मुख्य तकनीक को "कलर-कोडिंग" तकनीक (Alon, Yuster, and Zwick, 1995) का एक रूप माना गया है, जिसका उपयोग पैरामीटराइज्ड एल्गोरिदम में व्यापक रूप से किया जाता है। लेखक नोट करते हैं कि निर्माण मूल रूप से GPT-6 Astra द्वारा पाया गया था, लेकिन यह पेपर विचारों का मानव-प्रेरित पुनर्निर्माण और प्रमाण प्रदान करता है।

लेखक निष्कर्ष निकालते हैं कि हालांकि यह परिणाम मेजॉरिटी के लिए गैप को बंद करता है, फिर भी यह सुझाव देता है कि कॉन्स्टेंट डेप्थ में सुपर-पॉलीनोमियल साइज की आवश्यकता वाले स्पष्ट फंक्शन को खोजने के लिए (P को NP से अलग करने के लिए) अधिक जटिल फंक्शनों का अध्ययन करने की आवश्यकता हो सकती है, क्योंकि अब सबसे "सरल" उम्मीदवार पूरी तरह से चरित्रित (characterized) किए जा चुके हैं।

इसी तरह के और पेपर