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

The Complexity Landscape of Boolean Formula Isomorphism: From Graph Isomorphism to the Second Level

यह शोध पत्र कैनोनिकल फॉर्मूला आइसोमोर्फिज्म (canonical formula isomorphism) और ग्राफ आइसोमोर्फिज्म के बीच एक द्विदिश मेनी-वन तुल्यता (bidirectional many-one equivalence) स्थापित करते हुए, को-एनपी-कम्प्लीट (coNP-complete) समानता परीक्षण और अवशिष्ट ग्राफ आइसोमोर्फिज्म कोर के संयोजन के कारण सामान्य फॉर्मूला आइसोमोर्फिज्म के दूसरे स्तर ( $\Sigma_2^P$ ) पर स्थित होने को प्रदर्शित करते हुए, पॉलीनोमियल पदानुक्रम (polynomial hierarchy) के भीतर बुलियन फॉर्मूला आइसोमोर्फिज्म की जटिलता को सटीक रूप से वर्गीकृत करता है।

मूल लेखक: Francesco Cristiano

प्रकाशित 2026-11-05✓ Author reviewed ⓘ

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

CC BY 4.0

मूल लेखक: Francesco Cristiano

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

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

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

यह अध्ययन 'बुलियन फॉर्मूला आइसोमोर्फिज्म' (Boolean formula isomorphism) नामक एक विशिष्ट प्रकार की तर्क पहेली पर केंद्रित है। सरल शब्दों में, यह पूछता है: यदि आपके पास एक तर्क मशीन के लिए नियमों के दो अलग-अलग सेट हैं, तो क्या आप दूसरे सेट में चरों (variables) का नाम बदलकर उसे पहले वाले के समान बना सकते हैं? शोधकर्ता ने पाया कि उत्तर पूरी तरह से नियमों के प्रारूप (format) पर निर्भर करता है। यदि नियम एक बहुत ही विशिष्ट, विस्तारित प्रारूप में लिखे गए हैं जहाँ प्रत्येक संभावित परिणाम को सूचीबद्ध किया गया है, तो यह ग्राफ़ मिलान, या बिंदुओं और रेखाओं के नेटवर्क से संबंधित एक प्रसिद्ध पहेली के समकक्ष है। यह कठिनाई का एक ज्ञात स्तर है जिसने गणितज्ञों को वर्षों से उलझा रखा है। हालाँकि, यदि नियम एक संक्षिप्त, शॉर्टहैंड प्रारूप में लिखे गए हैं, तो समस्या बहुत उच्च स्तर की कठिनाई में कूद जाती है। यह एक दो-चरणीय चुनौती बन जाती है: पहले, आपको एक नया नाम (renaming) अनुमान लगाना होगा, और फिर आपको सत्यापित करना होगा कि पुनरनामित नियम मूल के समान हैं या नहीं। यह सत्यापन चरण इतना कठिन है कि यह पूरी समस्या को एक उच्च श्रेणी की जटिलता में धकेल देता है, जो ग्राफ़ पहेली से ऊपर है लेकिन पूर्णतः कठिन ज्ञात समस्याओं से नीचे है।

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

महत्वपूर्ण रूप से, शोध पत्र इस संभावना को भी खारिज करता है कि ये समस्याएं अपने संबंधित श्रेणियों में सबसे कठिन हैं, जब तक कि कंप्यूटर विज्ञान की संरचना में कोई बड़ा पतन (collapse) न हो जाए। यदि ये समस्याएं सबसे कठिन होतीं, तो इसका तात्पर्य यह होता कि कई अन्य समस्याएं जिन्हें हम अलग समझते हैं, वास्तव में एक ही हैं, एक ऐसा परिदृश्य जिसे अधिकांश विशेषज्ञ असंभव मानते हैं। शोधकर्ता प्रदर्शित करते हैं कि जब इनपुट संक्षिप्त होते हैं, तो ग्राफ़-पहेली की कठिनाई जटिलता के उच्च स्तरों में समाहित हो जाती है, जिसका अर्थ है कि संक्षिप्त प्रारूप की अतिरिक्त कठिनाई ग्राफ़ पहेली को पूरी तरह से निगल लेती है। इसका मतलब है कि संक्षिप्त संस्करणों के लिए, ग्राफ़ पहेली अब बाधा नहीं है; बाधा तर्क के सत्यापन (verification) में है।

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

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

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

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

तकनीकी सारांश: बूलियन फॉर्मूला आइसोमोर्फिज्म का जटिलता परिदृश्य

समस्या विवरण
यह शोध पत्र बूलियन फॉर्मूला आइसोमोर्फिज्म (FI) समस्या की कम्प्यूटेशनल जटिलता की जांच करता है। FI यह पूछता है कि क्या दो बूलियन फॉर्मूला, $F_1$ और $F_2$ , उनके चरों (variables) के किसी पुनरनामकरण (renaming/permutation) के तहत एक ही फलन (function) को दर्शाते हैं ( $F_1 \equiv F_2 \circ \lambda$ )। यह समस्या दो अलग-अलग जटिलता स्रोतों के मिलन बिंदु पर स्थित है:

सिमेंटिक जटिलता (Semantic Complexity): दो फॉर्मुलों के समान होने ( $F \equiv G$ ) का निर्णय लेने की लागत।
स्ट्रक्चरल जटिलता (Structural Complexity): एक ऐसा चर पुनरनामकरण $\lambda$ खोजने की खोज जो तुल्यता (equivalence) को संतुष्ट करता हो।

इस शोध पत्र का लक्ष्य FI और इसके वेरिएंट्स को 'पॉलिनोमियल हाइरार्की' (PH) के भीतर सटीक रूप से स्थापित करना है, यह विश्लेषण करते हुए कि इनपुट प्रतिनिधित्व (कैनोनिकल बनाम कॉम्पैक्ट) का इन दोनों घटकों पर क्या प्रभाव पड़ता है।

कार्यप्रणाली: गुणनखंड सिद्धांत (The Factorisation Principle)
मुख्य पद्धतिगत योगदान "गुणनखंड सिद्धांत" है, जिसे प्रमेय 1 में औपचारिक रूप दिया गया है। शोध पत्र यह स्थापित करता है कि किसी भी प्रतिनिधित्व वर्ग $\mathcal{R}$ के लिए, जो चर पुनरनामकरण के तहत बंद (closed) है, आइसोमोर्फिज्म समस्या $FI_{\mathcal{R}}$ को इस प्रकार विघटित किया जा सकता है:
$\langle A, B \rangle \in FI_{\mathcal{R}} \iff \exists \lambda : \langle A, B \circ \lambda \rangle \in EQ_{\mathcal{R}}$
जहाँ $EQ_{\mathcal{R}}$ वर्ग $\mathcal{R}$ के लिए तुल्यता (equivalence) की समस्या है।

यह विघटन प्रकट करता है कि:

पुनरनामकरण (Renaming) $\lambda$ , एक बहुपद-आकार के गवाह (polynomial-size witness) पर ठीक एक अस्तित्वगत क्वांटिफायर (existential quantifier) का योगदान देता है।
आइसोमोर्फिज्म समस्या की जटिलता स्तर (Complexity level), तुल्यता परीक्षण ( $EQ_{\mathcal{R}}$ ) की जटिलता द्वारा "कैप्ड" (सीमित) होती है।
अवशिष्ट संरचनात्मक जटिलता (Residual structural complexity) (अर्थात $\lambda$ खोजने की कठिनाई), उसी स्तर के भीतर अलग की जाती है।

शोध पत्र इस सिद्धांत को तीन विशिष्ट मामलों पर लागू करता है जो उनके इनपुट प्रतिनिधित्व द्वारा परिभाषित हैं:

कैनोनिकल इनपुट (CFI): दोनों इनपुट कैनोनिकल रूप में हैं (जैसे पूर्ण DNF/minterm सूचियाँ)। यहाँ, तुल्यता बहुपद समय में निर्णायक है ( $EQ \in P$ )।
मिक्स्ड इनपुट (DT-FI): एक इनपुट एक अनिश्चित (arbitrary) फॉर्मूला है, दूसरा एक लक्ष्य DNF है। तुल्यता coNP-पूर्ण (coNP-complete) है।
कॉम्पैक्ट इनपुट (CNF-FI): दोनों इनपुट कॉम्पैक्ट हैं (जैसे CNF फॉर्मूला)। तुल्यता coNP-पूर्ण है।

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

1. ग्राफ आइसोमोर्फिज्म (GI) के साथ संबंध को स्पष्ट करना

परिणाम: शोध पत्र सिद्ध करता है कि कैनोनिकल फॉर्मूला आइसोमोर्फिज्म (CFI), ग्राफ आइसोमोर्फिज्म (GI) के समान 'मैनी-वन रिडक्शन' (many-one equivalent) है, और इसका पूरक CFNI, ग्राफ नॉन-आइसोमोर्फिज्म (GNI) के समान है।
नवीनता: पूर्ववर्ती कार्य (चांग) ने स्थापित किया था कि अनियंत्रित बूलियन आइसोमोर्फिज्म एक दिशा में GI-हार्ड है। यह शोध पत्र कैनोनिकल इनपुट के लिए एक दो-दिशीय न्यूनीकरण (two-directional reduction) प्रदान करता है।
- कठिनाई ( $GI \le_m CFI$ ): "वेट-टू-मिन्टरम" (weight-two-minterm) एनकोडिंग के माध्यम से प्राप्त किया गया। ग्राफ के किनारों (edges) को हैमिंग वेट दो के मिन्टरम्स के रूप में एनकोड किया गया है। यह एनकोडिंग "रिजिड" (rigid) है, जो किसी भी चर पुनरनामकरण को मजबूर करती है कि वह ग्राफ आइसोमोर्फिज्म के अनुरूप हो।
- सदस्यता ( $CFI \le_m GI$ ): फॉर्मूला के ऑन-सेट (on-set) को एक बाइपार्टाइट ग्राफ के रूप में एनकोड करके और कलर गैजेट्स का उपयोग करके मानक GI में न्यूनीकरण के माध्यम से प्राप्त किया गया।
महत्व: यह CFI को केवल एक GI-हार्ड समस्या के बजाय GI के एक सटीक बूलियन एनालॉग के रूप में स्थापित करता है।

2. कॉम्पैक्ट और मिक्स्ड मामलों का वर्गीकरण

परिणाम: DT-FI (अनिश्चित फॉर्मूला बनाम DNF लक्ष्य) और CNF-FI (CNF बनाम CNF) दोनों ही पॉलिनोमियल हाइरार्की के दूसरे स्तर, $\Sigma_2^P$ में आते हैं।
कठिनाई (Hardness): दोनों समस्याएँ coNP-हार्ड (तुल्यता परीक्षण के कारण) और GI-हार्ड (संरचनात्मक पुनरनामकरण खोज के कारण) हैं।
Non-Completeness: CFI is not NP-complete, and CFNI is not coNP-complete, unless PH collapses to $\Sigma_2^P$ ; this uses $GNI \in AM$ , since CFNI is many-one equivalent to GNI. Neither DT-FI nor CNF-FI is $\Sigma_2^P$ -complete unless PH collapses to $\Sigma_3^P$ ; this uses the interactive proof of Agrawal and Thierauf for formula non-isomorphism ( $FNI \in BP\cdot\Sigma_2^P$ ).

3. लोनेस (Lowness) और पॉलिनोमियल हाइरार्की की भूमिका

GI का अवशोषण (Absorption of GI): शोध पत्र शोनिंग (Schöning) के 'लोनेस' परिणाम ( $\Sigma_k^P[GI] = \Sigma_k^P$ $k \ge 2$ के लिए) का उपयोग यह दिखाने के लिए करता है कि GI कोर $\Sigma_2^P$ स्तर पर "अवशोषित" हो जाता है। एक बार जब तुल्यता परीक्षण समस्या को $\Sigma_2^P$ तक धकेल देता है, तो GI ऑरेकल की अतिरिक्त शक्ति कुछ भी नहीं जोड़ती।
प्रथम-स्तर की सीमा (First-Level Boundary): शोध पत्र यह स्पष्ट करता है कि क्या GI, NP के लिए 'लो' है ( $NP^{GI} = NP$ ), यह इस बात के समान है कि क्या CFI, $NP \cap coNP$ में है। यह एक खुला प्रश्न बना हुआ है।
ध्वस्त होने की स्थितियाँ (Collapse Conditions): एक चार-मामला वर्गीकरण (कोरोलरी 1) प्रस्तुत किया गया है। GI स्तर केवल तभी PH के पतन को ट्रिगर कर सकता है जब GI, NP-पूर्ण हो (मामला 4), ऐसी स्थिति में PH $\Sigma_2^P$ पर ध्वस्त हो जाता। अन्य सभी संभावित परिदृश्यों में (GI $\in P$ , GI $\in NP \cap coNP$ , या GI $\in NP \setminus coNP$ लेकिन पूर्ण नहीं), कोई पतन नहीं होता।

महत्व और दावे
शोध पत्र का दावा है कि इसका प्राथमिक योगदान नए जटिलता वर्गों की खोज के बजाय एक एकीकृत वर्गीकरण ढांचा (unified classification framework) प्रदान करना है।

एकीकरण: यह प्रदर्शित करता है कि सभी फॉर्मूला आइसोमोर्फिज्म वेरिएंट की जटिलता एक एकल कारक द्वारा निर्धारित होती है: चुने गए प्रतिनिधित्व में तुल्यता की लागत। "पुनरनामकरण" घटक एक स्थिर संरचनात्मक अवशेष (GI) है जो इस सिमेंटिक लागत के ऊपर स्थित है।
परिष्करण: यह ग्राफ आइसोमोर्फिज्म के साथ बूलियन आइसोमोर्फिज्म के संबंध की समझ को परिष्कृत करता है, जो एक-तरफा हार्डनेस परिणाम से कैनोनिकल रूपों के लिए एक सटीक समानता की ओर बढ़ता है।
विनम्रता: शोध पत्र स्पष्ट रूप से कहता है कि यह खुले प्रश्नों (जैसे कि क्या GI, $NP \cap coNP$ में है) को हल नहीं करता है, बल्कि मौजूदा तथ्यों (जैसे कि शोनिंग की लोंनेस और GNI की AM समावेशन) को GI कोर के प्रभाव के संबंध में एक सुसंगत चार-मामला विश्लेषण में व्यवस्थित करता है।

निष्कर्ष
शोध पत्र निष्कर्ष निकालता है कि बूलियन फॉर्मूला आइसोमोर्फिज्म का जटिलता परिदृश्य प्रतिनिधित्व के "सिमेंटिक एक्सिस" (semantic axis) द्वारा शासित है। जब तुल्यता मुफ्त होती है (कैनोनिकल), तो समस्या ठीक ग्राफ आइसोमोर्फिज्म होती है। जब तुल्यता महंगी होती है (कॉम्पैक्ट), तो समस्या $\Sigma_2^P$ तक बढ़ जाती है, जहाँ ग्राफ आइसोमोर्फिज्म कोर संरचनात्मक रूप से मौजूद होता है लेकिन 'लोनेस' गुणों के कारण कम्प्यूटेशनल रूप से निष्क्रिय होता है। यह कार्य इस बात का एक निश्चित मानचित्र प्रदान करता है कि ये समस्याएँ हाइरार्की में कहाँ स्थित हैं और किन शर्तों के तहत (विशेष रूप से, यदि GI, NP-पूर्ण हो) हाइरार्की ध्वस्त होगी।

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