💻 computer science

A non-uniform view of Craig interpolation in modal logics with linear frames

यह शोध पत्र प्रदर्शित करता है कि जबकि K4.3 का विस्तार करने वाले सामान्य मोडल लॉजिक (modal logics) आम तौर पर क्रेग इंटरपोलेशन (Craig interpolation) गुण का अभाव रखते हैं, किसी दिए गए सूत्रों के जोड़े के लिए क्रेग इंटरपोलेन्ट (Craig interpolant) के अस्तित्व को निर्धारित करने की विशिष्ट समस्या निर्णयात्मक (decidable) और coNP-पूर्ण (coNP-complete) है, एक ऐसा परिणाम जो मानक रैखिक समय प्रवाह (standard linear time flows) पर प्रियोरन टेम्पोरल लॉजिक (Priorean temporal logics) पर भी लागू होता है।

मूल लेखक: Agi Kurucz, Frank Wolter, Michael Zakharyaschev

प्रकाशित 2026-06-19

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

CC BY 4.0

मूल लेखक: Agi Kurucz, Frank Wolter, Michael Zakharyaschev

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

कल्पना कीजिए कि आप एक जासूस हैं जो दो संदिग्धों, फार्मूला A और फार्मूला B से जुड़े एक रहस्य को सुलझाने की कोशिश कर रहे हैं। आप इस तथ्य को जानते हैं कि यदि A सत्य है, तो B को भी सत्य होना चाहिए (A implies B)।

तर्कशास्त्र (logic) की दुनिया में, एक विशेष नियम है जिसे क्रेग इंटरपोलेशन प्रॉपर्टी (Craig Interpolation Property) कहा जाता है। यह कहता है कि जब भी A, B को दर्शाता है, तो वहां एक "बिचौलिया" कथन होना चाहिए, जिसे हम I कह सकते हैं, जो एक सेतु (bridge) के रूप में कार्य करता है। इस बिचौलिया I का एक बहुत ही विशिष्ट कार्य है:

यह केवल उन्हीं शब्दों (variables) का उपयोग करता है जो A और B दोनों में मौजूद हैं।
A, I को दर्शाता है, और I, B को दर्शाता है।

सोचिए कि I एक अनुवादक (translator) है। यदि A "अंग्रेजी" बोल रहा है और B "फ्रेंच," तो बिचौलिया I एक ऐसा वाक्य है जो केवल साझा भाषाओं के शब्दों का उपयोग करता है, जो यह सिद्ध करता है कि A का अर्थ तार्किक रूप से B में प्रवाहित होता है।

समस्या: गायब हुआ सेतु (The Missing Bridge)

कई तार्किक प्रणालियों (जैसे मानक गणित या बुनियादी कंप्यूटर तर्क) के लिए, यह सेतु I हमेशा मौजूद होता है। लेकिन इस शोध पत्र के लेखक एक विशेष, जटिल प्रकार के लॉजिक पर विचार कर रहे हैं जिन्हें K4.3 और उनके संबंधी लॉजिक कहा जाता है। ये लॉजिक "रैखिक" (linear) दुनियाओं का वर्णन करते हैं—सोचिए जैसे समय अतीत से भविष्य की ओर एक सीधी रेखा में चल रहा हो, या एक कतार में खड़े लोगों की लाइन।

इन रैखिक दुनियाओं में, "ब्रिज रूल" (क्रेग इंटरपोलेशन प्रॉपर्टी) टूट जाता है। कभी-कभी, A, B को दर्शाता है, लेकिन वहां कोई बिचौलिया वाक्य I नहीं होता जो नियमों के अनुकूल हो। यह एक ऐसी बातचीत की तरह है जहाँ तर्क तो सही है, लेकिन आप साझा शब्दावली का उपयोग करके संबंध को समझाने वाला एक भी वाक्य नहीं ढूंढ पाते।

आमतौर पर, जब कोई लॉजिक इस नियम को तोड़ देता है, तो शोधकर्ता हाथ खड़े कर देते हैं और कहते हैं, "हमें एक सेतु नहीं मिल रहा, इसलिए हम अब इस संबंध का अध्ययन नहीं कर सकते।"

नया दृष्टिकोण: "क्या सेतु मौजूद है?" खेल

लेखकों ने एक अलग, "गैर-समान" (non-uniform) दृष्टिकोण अपनाया। पूरे लॉजिक के लिए यह पूछने के बजाय कि, "क्या हर जोड़े के वाक्यों के लिए एक सेतु हमेशा मौजूद होता है?" (जिसका उत्तर 'नहीं' है), उन्होंने एक अधिक व्यावहारिक प्रश्न पूछा:

"इन दो विशिष्ट वाक्यों, A और B के लिए, क्या एक सेतु मौजूद है?"

वे इसे इंटरपोलेंट अस्तित्व समस्या (Interpolant Existence Problem - IEP) कहते हैं। यह एक मैकेनिक से पूछने जैसा है: "क्या इस विशिष्ट कार में इंजन काम कर रहा है?" न कि यह पूछना कि "क्या इस फैक्ट्री की सभी कारों में इंजन हैं?"

बड़ी खोज: यह जांचना उतना कठिन नहीं है जितना कि वैधता (Validity) की जांच करना

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

कंप्यूटर विज्ञान के शब्दों में, यह पता लगाने की कठिनाई कि क्या एक सेतु मौजूद है, ठीक उतनी ही है जितनी कि मूल कथन (A implies B) के सत्य होने की जांच करने की कठिनाई। वे इस जटिलता को coNP-complete कहते हैं।

उपमा (Analogy):
कल्पना कीजिए कि आप नदी पार करने की कोशिश कर रहे हैं।

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

उन्होंने दिखाया कि इन रैखिक लॉजिक्स के लिए, आपको सुपर-कंप्यूटर की आवश्यकता नहीं है; एक मानक कंप्यूटर इसे कुशलतापूर्वक कर सकता है। यह एक बड़ी बात है क्योंकि अन्य समान तार्किक प्रणालियों में, यह पता लगाना कि क्या एक सेतु मौजूद है, मूल कथन की सत्यता की जांच करने की तुलना में बहुत अधिक कठिन होता है।

उन्होंने इसे कैसे किया: "डिस्क्रिप्टिव फ्रेम" मानचित्र

इसे हल करने के लिए, लेखकों ने डिस्क्रिप्टिव फ्रेम्स (descriptive frames) नामक उपकरण का उपयोग किया। कल्पना कीजिए कि ये तार्किक दुनिया के विस्तृत, उच्च-रिज़ॉल्यूशन वाले मानचित्र हैं।

कभी-कभी, ये मानचित्र सरल, परिमित रेखाओं की तरह दिखते हैं।
कभी-कभी, ये अनंत क्लस्टरों (समूहों) की श्रृंखलाओं की तरह दिखते हैं जो अनंत तक फैलते हैं, जैसे कि एक "टैडपोल" (tadpole) का आकार, जिसमें एक सिर और एक अनंत पूंछ होती है।

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

उन्होंने इस पद्धति को लागू किया:

मानक रैखिक लॉजिक: सीधी रेखाओं का लॉजिक (K4.3)।
टेम्पोरल लॉजिक (Temporal Logics): वे लॉजिक जो "भविष्य" और "अतीत" दोनों को संभालते हैं (जैसे समय)। उन्होंने पूर्णांक (Integers) (..., -2, -1, 0, 1, 2...), परिमेय संख्या (Rationals), वास्तविक संख्या (Reals) और परिमित (Finite) समय जैसे विशिष्ट समय प्रवाहों को देखा।

इन सभी के लिए, उन्होंने सिद्ध किया कि सेतु की जांच करना गणनात्मक रूप से प्रबंधनीय (coNP-complete) है।

निष्कर्ष (The Takeaway)

यह शोध पत्र एक "नकारात्मक" तथ्य (कि इन लॉजिक्स में इंटरपोलेशन प्रॉपर्टी नहीं है) को एक सकारात्मक शोध प्रश्न में बदल देता है। उन्होंने दिखाया कि भले ही इन रैखिक दुनियाओं में "परफेक्ट ब्रिज" का नियम टूट जाता है, फिर भी हम किसी विशिष्ट स्थिति के लिए यह कुशलतापूर्वक तय कर सकते हैं कि क्या एक सेतु मौजूद है।

संक्षेप में: सिर्फ इसलिए कि इन रैखिक दुनियाओं में "परफेक्ट ब्रिज" का नियम टूट गया है, इसका मतलब यह नहीं है कि हम अंधेरे में फंसे हुए हैं। हमारे पास एक विश्वसनीय, कुशल टॉर्च है जिससे हम किसी भी वाक्यों के जोड़े के लिए यह जांच सकते हैं कि क्या कोई रास्ता मौजूद है।

तकनीकी सारांश: रैखिक ढांचों (Linear Frames) वाले मोडल लॉजिक्स में क्रेग इंटरपोलेशन का एक गैर-समान दृष्टिकोण

समस्या विवरण (Problem Statement)
क्रेग इंटरपोलेशन प्रॉपर्टी (CIP) तर्कशास्त्र में एक मौलिक गुण है जो यह बताता है कि किसी भी वैध निहितार्थ (valid implication) $\phi \to \psi$ के लिए, एक इंटरपुलेंट (interpolant) $\iota$ मौजूद होता है, जो $\phi$ और $\psi$ के साझा शब्दावली (shared vocabulary) का उपयोग करता है, ताकि $\phi \to \iota$ और $\iota \to \psi$ भी वैध हों। यह एक सुस्थापित "नकारात्मक" तथ्य है कि कई सामान्य मोडल लॉजिक्स, जो K4.3 (रैखिक अनुक्रमिक ढांचों का तर्क) का विस्तार करते हैं, CIP का अभाव रखते हैं, विशेष रूप से वे जिनमें अनबाउंडेड गहराई (unbounded depth) वाले ढांचे होते हैं। पारंपरिक रूप से, CIP की अनुपस्थिति ने दिए गए लॉजिक के लिए इंटरपुलेंट्स के अनुसंधान को समाप्त कर दिया था।

यह शोध पत्र CIP की अनुपस्थिति को एक शोध प्रश्न के रूप में पुनर्गठित करता है, जिसमें इंटरपुलेंट अस्तित्व समस्या (Interpolant Existence Problem - IEP) की जांच की जाती है: यदि $\phi \to \psi$ किसी लॉजिक $L$ में वैध है, तो क्या $L$ में एक क्रेग इंटरपुलेंट मौजूद है? यूनिफॉर्म CIP के विपरीत, IEP केवल वैधता जाँच (validity checking) तक सीमित नहीं है क्योंकि निहितार्थ की वैधता इंटरपुलेंट के अस्तित्व की गारंटी नहीं देती है। केंद्रीय प्रश्न यह है कि क्या IEP इन लॉजिक्स के लिए वैधता समस्या (entailment) की तुलना में गणनात्मक रूप से अधिक कठिन (computationally harder) है। अन्य लॉजिक्स (जैसे, номинаल्स वाले मोडल लॉजिक्स, प्रथम-क्रम तर्क के अंश) के पिछले परिणामों ने सुझाव दिया था कि IEP काफी कठिन (जैसे, 3ExpTime) हो सकता है। यह शोध पत्र जांच करता है कि क्या K4.3 वाले प्रोपोज़िशनल मोडल लॉजिक्स के लिए भी यही स्थिति है।

कार्यप्रणाली (Methodology)
लेखक बिसिम्यूलेशन (bisimulations) और डिस्क्रिप्टिव फ्रेम्स (descriptive frames) पर आधारित एक गैर-समान, मॉडल-सैद्धांतिक दृष्टिकोण का उपयोग करते हैं।

बिसिम्यूलेशन लक्षण वर्णन (Bisimulation Characterization): शोध पत्र एक ज्ञात मानदंड (थ्योरम 3.2) का उपयोग करता है जो कहता है कि $\phi \to \psi$ में $L$ में एक इंटरपुलेंट का अभाव है यदि और केवल यदि दो मॉडल, $M_1$ और $M_2$ , $L$ के लिए डिस्क्रिप्टिव फ्रेम्स पर आधारित, ऐसे मौजूद हैं कि $M_1$ $\phi$ को संतुष्ट करता है, $M_2$ $\neg\psi$ को संतुष्ट करता है, और इन मॉडलों के रूट पॉइंट्स $\sigma$ -बिसिमिलर (जहाँ $\sigma$ साझा सिग्नेचर है) हैं।
डिस्क्रिप्टिव फ्रेम्स (Descriptive Frames): विश्लेषण अत्यधिक रूप से डिस्क्रिप्टिव फ्रेम्स (एक विशिष्ट आंतरिक सेट के बीजगणित से सुसज्जित ढांचे जो विभेदन, कसाव और कॉम्पैक्टनेस की शर्तों को पूरा करते हैं) की संरचना पर निर्भर करता है। यह GL.3 और Log{(N, <)} जैसे लॉजिक्स के लिए महत्वपूर्ण है क्योंकि, इन लॉजिक्स में CIP के विरुद्ध काउंटर-एग्जांपल मानक क्रिपके फ्रेम्स (Kripke frames) द्वारा नहीं देखे जा सकते, बल्कि इनके लिए अनंत डिस्क्रिप्टिव फ्रेम्स की आवश्यकता होती है।
संरचनात्मक अपघटन (Structural Decomposition): मुख्य तकनीकी नवाचार इन बिसिमिलर मॉडलों की संरचना का विश्लेषण करना है। लेखक इन मॉडलों को $\sigma$ -ब्लॉक्स ( $\sigma$ -blocks - विशिष्ट बिसिम्यूलेशन गुणों वाले बिंदुओं के अंतराल) में विभाजित करते हैं और दिखाते हैं कि इंटरपुलेंट की कमी को प्रमाणित करने वाले किसी भी बिसिमिलर मॉडल के जोड़े को "क्वासी-फाइनाइट" (quasi-finite) मॉडलों के जोड़े में बदला जा सकता है। ये मॉडल विशिष्ट एटॉमिक फ्रेम्स (परिमित श्रृंखलाएं, परिमित क्लस्टर, या $C(\bigcirc_k, \bullet)$ जैसे "टैडपोल" संरचनाएं) पर आधारित सिंपल मॉडल्स के क्रमबद्ध योग (ordered sums) के रूप में निर्मित किए जाते हैं।
क्वासी-पॉलीसाइज़ प्रॉपर्टी (Quasi-Polysize Property): फाइनाइटली एक्सिओमैटाइज्ड (finitely axiomatisable) लॉजिक्स के लिए, लेखक सिद्ध करते हैं कि इन साक्षी मॉडलों (witnessing models) का आकार इनपुट फॉर्मुलों और लॉजिक के एक्सिओम्स के आकार के बहुपद (polynomial) द्वारा सीमित किया जा सकता है। इसे क्वासी-पॉलीसाइज़ बिसिमिलर मॉडल प्रॉपर्टी कहा जाता है।

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

निर्णयक्षमता और जटिलता (Decidability and Complexity): शोध पत्र सिद्ध करता है कि सभी फाइनाइटली एक्सिओमैटाइज्ड नॉर्मल मोडल लॉजिक्स, जो K4.3 का विस्तार करते हैं, के लिए IEP निर्णयक्षम (decidable) और coNP-complete है।
- यह परिणाम महत्वपूर्ण है क्योंकि यह दिखाता है कि IEP वैधता समस्या (जो इन लॉजिक्स के लिए coNP में भी है) से अधिक कठिन नहीं है। यह अन्य लॉजिकल फ्रेमवर्क में हाल के गैर-यूनिफॉर्म इंटरपोलेशन परिणामों के बिल्कुल विपरीत है जहाँ IEP स्पष्ट रूप से अधिक कठिन है।
- प्रमाण में एक नॉन-डिटरमिनिस्टिक एल्गोरिदम शामिल है जो बिसिम्यूलेशन मानदंड को संतुष्ट करने वाले पॉलीनोमियल-साइज़ मॉडल का अनुमान लगाता है और लॉजिक के एक्सिओम्स को सत्यापित करता है।
क्वासी-पॉलीसाइज़ बिसिमिलर मॉडल प्रॉपर्टी: लेखक स्थापित करते हैं कि K4.3 के सभी फाइनाइटली एक्सिओमैटाइज्ड विस्तार "क्वासी-पॉलीसाइज़ बिसिमिलर मॉडल प्रॉपर्टी" रखते हैं। इसका अर्थ है कि यदि एक इंटरपुलेंट मौजूद नहीं है, तो एक जोड़ी बिसिमिलर मॉडल मौजूद है जो इस तथ्य को प्रमाणित करता है जहाँ मॉडल एटॉमिक फ्रेम्स के पॉलीनोमियल आकार के एक पॉलीनोमियल संख्या में सिंपल मॉडल्स के क्रमबद्ध योग हैं।
- d-पर्सिस्टेंट कोफिनल सबफ्रेम लॉजिक्स (एक उपवर्ग) के लिए, यह गुण और भी मजबूत है: उनमें पॉलीसाइज़ बिसिमिलर मॉडल प्रॉपर्टी है, जहाँ मॉडल पॉलीनोमियल आकार के मानक क्रिपके फ्रेम्स हैं।
प्रियोरन टेम्पोरल लॉजिक्स (Priorean Temporal Logics) तक विस्तार: कार्यप्रणाली को मानक समय प्रवाह (standard time flows) पर प्रियोरन टेम्पोरल लॉजिक्स (जिसमें भविष्य और अतीत दोनों मोडलिटीज शामिल हैं) पर विस्तारित किया गया है:
- Lin (सभी रैखिक ढांचे), LinQ (परिमेय संख्याएँ), और LinR (वास्तविक संख्याएँ): इन्हें पॉलीसाइज़ बिसिमिलर मॉडल प्रॉपर्टी प्राप्त है, और इनका IEP coNP-complete है।
- Lin<ω (परिमित सख्त रैखिक क्रम) और LinZ (पूर्णांक): इनमें पॉलीसाइज़ प्रॉपर्टी नहीं है लेकिन क्वासी-पॉलीसाइज़ बिसिमिलर मॉडल प्रॉपर्टी है। इनका IEP भी coNP-complete सिद्ध किया गया है।
- टेम्पोरल लॉजिक्स के प्रमाण के लिए दोनों दिशाओं में द्विदिश श्रृंखलाओं (bidirectional chains) और लिमिट क्लस्टर्स को संभालना आवश्यक है, जिसके लिए नए फ्रेम निर्माण (जैसे, सममित "टैडपोल" फ्रेम $C(\bullet, \bigcirc_k, \bullet)$ ) की आवश्यकता होती है।

महत्व और दावे (Significance and Claims)
शोध पत्र का दावा है कि यह उन मोडल लॉजिक्स (K4.3 के विस्तार) के एक बड़े परिवार को कवर करने वाला पहला सामान्य परिणाम प्रदान करता है जो CIP का अभाव रखते हैं। यह प्रदर्शित करके कि इन लॉजिक्स के लिए IEP coNP-complete है, लेखक इस अंतर्ज्ञान को चुनौती देते हैं कि CIP की अनुपस्थिति अनिवार्य रूप से अस्तित्व समस्या के लिए उच्च जटिलता वर्ग (complexity class) की ओर ले जाती है।

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

शोध पत्र स्पष्ट रूप से नोट करता है कि इसका प्रमाण इंटरपुलेंट्स के कंप्यूटेशन के संबंध में रचनात्मक (constructive) नहीं है; यह अस्तित्व के लिए एक निर्णय प्रक्रिया (decision procedure) प्रदान करता है लेकिन स्वयं इंटरपुलेंट को कंप्यूट करने या उसके आकार पर ऊपरी सीमा (upper bounds) देने के लिए कुशल एल्गोरिदम प्रदान नहीं करता है। लेखक भी इस बात पर जोर देते हैं कि उनके प्रमाण के लिए डिस्क्रिप्टिव फ्रेम्स आवश्यक हैं, जो यह खुला प्रश्न छोड़ते हैं कि क्या वे लॉजिक्स जो d-पर्सिस्टेंट नहीं हैं लेकिन स्ट्रॉन्गली क्रिपके कंप्लीट (जैसे, LinR) हैं, उनके लिए Kripke फ्रेम्स पर्याप्त होंगे।

समस्या: गायब हुआ सेतु (The Missing Bridge)

नया दृष्टिकोण: "क्या सेतु मौजूद है?" खेल

बड़ी खोज: यह जांचना उतना कठिन नहीं है जितना कि वैधता (Validity) की जांच करना

उन्होंने इसे कैसे किया: "डिस्क्रिप्टिव फ्रेम" मानचित्र

निष्कर्ष (The Takeaway)

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