कल्पना कीजिए कि आप एक विशाल, अराजक शहर में अपने एक विशिष्ट मित्र को खोजने की कोशिश कर रहे हैं। आपके पास एक मानचित्र (डेटाबेस) है जो दिखाता है कि लोग अभी कहाँ हैं, लेकिन आपके पास एक नियम पुस्तिका (ऑन्टोलॉजी) भी है जो उन चीजों के बारे में बताती है जो मानचित्र सीधे तौर पर नहीं दिखाता। उदाहरण के लिए, नियम पुस्तिका कह सकती है, "यदि एलिस बॉब की मित्र है, तो बॉब एलिस का मित्र है," या "यदि आप किसी का अनुसरण करते हैं, तो आप उनसे जुड़े हुए हैं।" कंप्यूटर विज्ञान की दुनिया में, इसे ऑन्टोलॉजी-मीडिएटेड क्वेरी अनswering (ontology-mediated query answering) कहा जाता है। यह एक बहुत ही बुद्धिमान मार्गदर्शक की तरह है जो केवल कच्चे डेटा को नहीं देखता, बल्कि रिक्त स्थानों को भरने के लिए तर्क का उपयोग करता है, जिससे दुनिया की कहीं अधिक पूर्ण तस्वीर मिलती है।

हालाँकि, प्रश्न पूछना तब जटिल हो जाता है जब आप रास्तों (paths) के बारे में पूछना शुरू करते हैं। केवल यह पूछने के बजाय कि, "क्या एलिस बॉब की मित्र है?" आप पूछ सकते हैं, "क्या मैं दोस्तों की एक श्रृंखला का अनुसरण करके एलिस से बॉब तक पहुँच सकता हूँ, भले ही वह श्रृंखला बहुत लंबी हो और घूमकर वापस आती हो?" इन्हें पाथ क्वेरीज़ (path queries) कहा जाता है। ये सोशल मीडिया या सिमेंटिक वेब जैसे जटिल नेटवर्क में नेविगेट करने के लिए आवश्यक हैं। लेकिन यहाँ एक पेंच है: जब आप इन पाथ क्वेरीज़ को एक शक्तिशाली नियम पुस्तिका के साथ जोड़ते हैं, तो कंप्यूटर का काम अविश्वसनीय रूप से कठिन हो जाता है, कभी-कभी इसे हल करना असंभव भी हो जाता है। मुख्य सवाल जिसके साथ वैज्ञानिक जूझ रहे हैं, वह यह है: विभिन्न प्रकार की नियम पुस्तिकाओं के साथ इन पाथ प्रश्नों को हल करना वास्तव में कितना कठिन है?

यह शोध पत्र एक समूह के जासूसों (जीन-फ्रांकोइस बागेट, मेघिन बिएनवेन्यू, मैरी-लौर मुग्नियर और माइकल थॉमज़ो) की तरह है जिन्होंने दो बहुत लोकप्रिय प्रकार की नियम पुस्तिकाओं के लिए इन पाथ क्वेरीज़ की कठिनाई को मैप करने का निर्णय लिया: लीनियर रूल्स (Linear Rules) और गार्डेड रूल्स (Guarded Rules)। "लीनियर रूल्स" को सरल, एक-चरणीय निर्देशों के रूप में सोचें (जैसे "यदि A सत्य है, तो B सत्य है"), और "गार्डेड रूल्स" को थोड़े अधिक जटिल निर्देशों के रूप में जो एक विशिष्ट "गार्डियन" तथ्य की उपस्थिति की आवश्यकता रखते हैं (जैसे "यदि A सत्य है और B सत्य है, तो C सत्य है")। लेखकों ने केवल अनुमान नहीं लगाया; उन्होंने सटीक रूप से सिद्ध किया कि इन पहेलियों को हल करने के लिए कितनी कंप्यूटिंग शक्ति की आवश्यकता होती है, जिससे उन्होंने वैज्ञानिकों के लिए एक सटीक "कठिनाई चार्ट" तैयार किया।

जासूसी कार्य: कठिनाई का मानचित्रण

लेखकों ने इस समस्या को इस तरह से हल किया जैसे कि वे कंप्यूटर की तर्क प्रक्रिया को "पीछा करने" के खेल की तरह देखते हैं। कल्पना करें कि एक खेल है जहाँ आप कुछ ज्ञात तथ्यों के साथ शुरू करते हैं और नए तथ्य उत्पन्न करने के लिए नियमों को लागू करना जारी रखते हैं जब तक कि आप और अधिक नहीं बना सकते। इसे चेस (chase) कहा जाता है। पाथ क्वेरीज़ के साथ चुनौती यह है कि "चेस" अनंत काल तक चल सकता है, जिससे कनेक्शन का एक अनंत जाल बन जाता है। शोधकर्ता जानना चाहते थे: क्या हम खेल को जल्दी रोक सकते हैं और फिर भी उत्तर जान सकते हैं? और एक पथ मौजूद है या नहीं, इसकी जाँच करने में कितना समय लगता है?

उन्होंने अपनी जांच को दो मुख्य परिदृश्यों में विभाजित किया: डेटा कॉम्प्लेक्सिटी (Data Complexity) (यह कितना कठिन है जब नियम पुस्तिका छोटी और स्थिर है, लेकिन शहर बहुत बड़ा है?) और कंबाइंड कॉम्प्लेक्सिटी (Combined Complexity) (यह कितना कठिन है जब नियम पुस्तिका और शहर दोनों ही विशाल हों?)।

सरल नियम: लीनियर रूल्स (Linear Rules)

सबसे पहले, उन्होंने लीनियर रूल्स को देखा। ये वे "सरल" नियम हैं जहाँ नियम का आधार (body) केवल एक एकल तथ्य होता है।

• खोज: उन्होंने पाया कि यदि आप केवल एक विशिष्ट डेटासेट को देख रहे हैं (डेटा कॉम्प्लेक्सिटी), तो इन पाथ प्रश्नों का उत्तर देना आश्चर्यजनक रूप से आसान है। यह एक फोन पर साधारण भूलभुलैया (maze) को नेविगेट करने जितना आसान है; कंप्यूटर इसे NL-complete समय में कर सकता है। यह बिना किसी नियम पुस्तिका के एक सादे मानचित्र पर पाथ प्रश्नों का उत्तर देने की गति के समान है!
• पेंच: यदि आप स्वयं नियमों को बदलना शुरू करते हैं (कंबाइंड कॉम्प्लेक्सिटी), तो चीजें कठिन हो जाती हैं। यदि नियम सरल और छोटे हैं, तो भी यह प्रबंधनीय है (PTime)। लेकिन यदि नियम मनमाने ढंग से लंबे और जटिल हो सकते हैं, तो कठिनाई ExpTime-complete तक बढ़ जाती है। इसका मतलब है कि समस्या को हल करने के लिए आवश्यक समय तेजी से बढ़ता है, जैसे पहाड़ के नीचे लुढ़कता हुआ हिमखंड, लेकिन यह अभी भी हल करने योग्य है।

जटिल नियम: गार्डेड रूल्स (Guarded Rules)

इसके बाद, उन्होंने गarder रूल्स पर काम किया। ये अधिक शक्तिशाली और लचीले हैं, जो अधिक जटिल संबंधों की अनुमति देते हैं, लेकिन इनके साथ एक "गार्ड" आता है जिसे संतुष्ट करना आवश्यक है।

• खौफनाक खोज: यहाँ, लेखकों ने एक चतुर चाल का उपयोग किया। उन्होंने दिखाया कि आप इन जटिल "गार्डेड" नियमों को सरल "लीनियर" नियमों में अनुवादित कर सकते हैं, लेकिन एक ट्विस्ट के साथ: यह अनुवाद नियमों के सेट के आकार को विस्फोट की तरह बढ़ा देता है।
• परिणाम: इस विस्फोट के कारण, गार्डेड नियमों के तहत पाथ प्रश्नों का उत्तर देना काफी कठिन है। सामान्य मामले (अनबाउंड अरिटी) में, कठिनाई 2ExpTime-complete तक बढ़ जाती है। यह एक दोहरी-घातांकीय (double-exponential) छलांग है, जिसका अर्थ है कि आवश्यक समय इतनी तेजी से बढ़ता है कि यह लगभग अकल्पनीय है। हालाँकि, यदि आप नियमों के आकार को सीमित करते हैं (बाउंडेड अरिटी), तो यह गिरकर ExpTime-complete हो जाता है, जो इन नियमों के तहत मानक प्रश्नों (केवल पाथ प्रश्न नहीं) का उत्तर देने की कठिनाई स्तर के समान है।

"लूप" और "प्रूफ स्कीम"

उन्होंने यह सब कैसे सिद्ध किया? उन्होंने कुछ शानदार मानसिक उपकरण बनाए।

लीनियर रूल्स के लिए, उन्होंने महसूस किया कि भले ही "चेस" एक अनंत जाल बनाता है, लेकिन कोई भी पथ जो "अज्ञात" (चेस का अज्ञात हिस्सा) में भटक जाता है और वापस एक ज्ञात तथ्य पर आता है, उसे एक एकल मूल तथ्य के "छाया" के भीतर से ही शुरू और समाप्त होना चाहिए। उन्होंने इन्हें "लूप्स" (loops) कहा। प्रत्येक प्रकार के तथ्य के लिए सभी संभावित लूप्स की पूर्व-गणना करके, वे एक "चीट शीट" (तालिका) बना सकते हैं जो कंप्यूटर को अनंत चेस का अनुकरण किए बिना पथ का अनुमान लगाने की अनुमति देती है। यही कारण है कि डेटा कॉम्प्लेक्सिटी इतनी कम है; कंप्यूटर बस चीट शीट में लूप को देखता है।

CRPQs (जो यहाँ तक कि अधिक जटिल पाथ क्वेरीज़ हैं जो एक साथ कई पथों के बारे में पूछ सकती हैं) के लिए, उन्होंने "प्रूफ स्कीम्स" (Proof Schemes) की अवधारणा का उपयोग किया। कल्पना कीजिए कि एक प्रूफ स्कीम अनंत चेस का एक छोटा, परिमित ब्लूप्रिंट है। पूरे अनंत शहर को बनाने के बजाय, कंप्यूटर एक छोटा, प्रतिनिधि मॉडल बनाता है जो सिद्ध करता है कि एक पथ मौजूद है। उन्होंने दिखाया कि यदि कोई पथ मौजूद है, तो हमेशा एक "छोटा" ब्लूप्रिंट होता है जो उसे सिद्ध करता है। इसने उन्हें यह सिद्ध करने में मदद की कि भले ही समस्या कठिन है, लेकिन यह असंभव नहीं है—बस इसके लिए बहुत अधिक मेमोरी और समय की आवश्यकता होती है।

उन्होंने क्या नहीं पाया (और यह क्यों महत्वपूर्ण है)

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

वे यह भी स्पष्ट करते हैं कि जबकि उनके परिणाम गणितीय रूप से सिद्ध हैं, सबसे कठिन मामलों (जैसे 2ExpTime वाले) के लिए एल्गोरिदम वर्तमान में वास्तविक दुनिया के उपयोग के लिए बहुत धीमे हैं। वे सैद्धांतिक मानचित्र हैं, न कि चलने के लिए तैयार कारें। हालाँकि, सरल लीनियर नियमों के लिए, वे सुझाव देते हैं कि उनके "लूप" तरीके को एक तेज़, व्यावहारिक उपकरण में बदला जा सकता है, विशेष रूप रूप से यदि उपयोगकर्ता के प्रश्न पूछने से पहले डेटा को अंतराल भरने के लिए प्रीप्रोसेस किया जाए।

बड़ी तस्वीर

अंत में, यह शोध पत्र दो प्रमुख प्रकार के तार्किक नियमों के तहत पाथ क्वेरीज़ को नेविगेट करने के लिए पहला पूर्ण "कठिनाई मानचित्र" प्रदान करता है। यह हमें बताता है कि:

1. सरल नियम (लीनियर) डेटा-भारी कार्यों के लिए बेहतरीन हैं क्योंकि वे तेज़ होते हैं, भले ही पथ जटिल हों।
2. शक्तिशाली नियम (गार्डेड) लचीले हैं लेकिन भारी कंप्यूटेशनल लागत के साथ आते हैं, विशेष रूप से जब नियम लंबे होते हैं।
3. पाथ क्वेरीज़ मानक प्रश्नों की तुलना में मौलिक रूप से कठिन हैं, लेकिन अब हम जानते हैं कि वे वास्तव में कितनी कठिन हैं।

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