💻 computer science

A Non-Binary Method for Finding Interpolants: Theory and Practice

यह शोधपत्र शास्त्रीय तर्कशास्त्र (classical logic) में इंटरपोलेन्ट्स (interpolants) खोजने के लिए एक नवीन विधि प्रस्तुत करता है जो एक खंडन-आधारित दृष्टिकोण (refutation-based approach) का लाभ उठाती है और अपने आधारभूत तंत्र के रूप में रिज़ॉल्यूशन (resolution) के एक गैर-बाइनरी संस्करण का उपयोग करती है।

मूल लेखक: Adam Trybus, Karolina Rożko, Tomasz Skura

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

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

CC BY 4.0

मूल लेखक: Adam Trybus, Karolina Rożko, Tomasz Skura

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

यहाँ "A Non-Binary Method for Finding Interpolants" पेपर का सरल भाषा और रचनात्मक उपमाओं के साथ अनुवाद दिया गया है।

बड़ी तस्वीर: यह पेपर किस बारे में है?

कल्पना कीजिए कि आप एक जासूस हैं जो एक रहस्य सुलझाने की कोशिश कर रहे हैं। आपके पास दो सबूत हैं: सुराग A और सुराग B। आप इस तथ्य को जानते हैं कि यदि सुराग A सत्य है, तो सुराग B को भी सत्य होना ही चाहिए ( $A \rightarrow B$ )।

आपका काम एक गुप्त संदेश (जिसे इंटरपोलांट कहा जाता है) खोजना है जो उनके बीच एक सेतु (ब्रिज) का काम करे। यह गुप्त संदेश निम्नलिखित शर्तों को पूरा करना चाहिए:

यह केवल उन्हीं तथ्यों से बना होना चाहिए जो सुराग A और सुराग B दोनों में मौजूद हैं।
यह इतना मजबूत होना चाहिए कि सिद्ध कर सके कि A इसके ओर ले जाता है।
यह इतना मजबूत होना चाहिए कि सिद्ध कर सके कि यह B की ओर ले जाता है।

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

मूल अवधारणा: "मिरर" (दर्पण) प्रणाली

अधिकांश तर्क प्रणालियाँ (logic systems) एक बिल्डर (निर्माता) की तरह काम करती हैं। वे किसी कथन को सत्य सिद्ध करने के लिए तर्क की ईंटों को एक के ऊपर एक रखने की कोशिश करती हैं।

लेखकों ने एक डिमोलिशन क्रू (ध्वस्त करने वाली टीम) दृष्टिकोण अपनाने का निर्णय लिया (जिसे वे रिफ्यूटेशन सिस्टम कहते हैं)। कुछ सत्य सिद्ध करने के बजाय, वे पूछते हैं: "हम यह कैसे सिद्ध कर सकते हैं कि यह FALSE (असत्य) है?"

बिल्डर: "मैं इन ईंटों से एक घर बना सकता हूँ।"
डिमोलिशन क्रू: "मैं इस घर को गिरा सकता हूँ क्योंकि ये ईंटें आपस में फिट नहीं बैठतीं।"

लेखकों ने महसूस किया कि यदि आप आसानी से यह पता लगा सकते हैं कि कोई तार्किक कथन क्यों टूट रहा है (असत्य है), तो आप उस "तोड़ने" की प्रक्रिया का उपयोग करके गुप्त संदेश (इंटरपोलांट) खोज सकते हैं। यह एक दीवार में कमजोर बिंदु खोजने जैसा है; एक बार जब आप जान जाते हैं कि दीवार कहाँ कमजोर है, तो आप उस खाली जगह पर एक पुल बना सकते हैं।

पुराना तरीका बनाम नया तरीका

पुराना तरीका (बाइनरी रेज़ोल्यूशन):
कल्पना कीजिए कि आप पहेली के दो टुकड़ों को जोड़ने की कोशिश कर रहे हैं। पुराना तरीका कहता है: "बाएँ से एक टुकड़ा चुनें, दाएँ से एक टुकड़ा चुनें, और देखें कि क्या वे फिट होते हैं। यदि वे फिट होते हैं, तो उन्हें चिपका दें। फिर एक और जोड़ी चुनें।"

समस्या: आपको यह एक समय में एक जोड़ी करके करना पड़ता है। यह एक विशाल पिज्जा को एक-एक स्लाइस करके खाने जैसा है। यह काम करता है, लेकिन इसमें बहुत समय लगता है।

नया तरीका (नॉन-बाइनरी रेज़ोल्यूशन):
लेखकों की विधि एक ही बार में पूरे पिज्जा को देखने जैसी है। वे कहते हैं: "आइए बायीं ओर के सभी स्लाइस और दाईं ओर के सभी स्लाइस को देखते हैं। हम एक पैटर्न देखते हैं जहाँ बायीं ओर का एक 'पेपरोनी' दाईं ओर के 'मशरूम' को रद्द कर देता है। आइए उन सभी जोड़ियों को एक साथ हटा दें और देखें कि क्या बचता है।"

लाभ: आप छोटे चरणों को छोड़ देते हैं। आप मेज को बहुत तेज़ी से साफ कर सकते हैं। पेपर का दावा है कि यह विधि पारंपरिक विधि की तुलना में कम चरणों में उत्तर खोज सकती है।

एल्गोरिदम कैसे काम करता है (जादुई ट्रिक)

पेपर एक चरण-दर-चरण रेसिपी (एल्गोरिदम) का वर्णन करता है जिसका एक कंप्यूटर पालन करता है। यहाँ सरल अंग्रेजी में रेसिपी दी गई है:

समस्या से शुरुआत करें: आपके पास एक कथन "यदि A, तो B" है जो निश्चित रूप से सत्य है।
एक वेरिएबल चुनें: एक अक्षर (जैसे $p$ ) खोजें जो A और B दोनों में दिखाई देता है, लेकिन विपरीत रूपों में (एक $p$ है, दूसरा "not $p$ ")।
दुनिया को विभाजित करें: दो समानांतर ब्रह्मांडों की कल्पना करें:
- ब्रह्मांड 1: मान लें कि $p$ सत्य है।
- ब्रह्मांड 2: मान लें कि $p$ असत्य है।
सरल बनाएं: प्रत्येक ब्रह्मांड में, समीकरणों से $p$ और "not $p$ " को हटा दें। अब आपके पास दो सरल समस्याएँ हैं।
दोहराएं: इन नई, सरल समस्याओं के लिए अगले अक्षर के लिए यही प्रक्रिया दोहराएं। विभाजित करना और सरल बनाना तब तक जारी रखें जब तक कि आप एक "बेस केस" तक न पहुँच जाएँ।
- बेस केस: आपके पास अक्षर खत्म हो जाते हैं। इस बिंदु पर, गणित गारंटी देता है कि या तो बायां पक्ष असंभव (False) है या दायां पक्ष सुनिश्चित (True) है।
पुनर्निर्माण करें: अब, सीढ़ी पर वापस ऊपर की ओर चलें। दोनों ब्रह्मांडों के उत्तरों को मिलाएं।
- यदि ब्रह्मांड 1 का उत्तर "False" था और ब्रह्मांड 2 का उत्तर "True" था, तो आप उन्हें अपने गुप्त संदेश को बनाने के लिए मिलाते हैं।
परिणाम: आपको एक फॉर्मूला मिलता है जो केवल साझा अक्षरों का उपयोग करता है और A तथा B के बीच के संबंध को सिद्ध करता है।

"इंसान बनाम रोबोट" की समस्या

लेखकों ने इसे टेस्ट करने के लिए एक कंप्यूटर प्रोग्राम (Python में) लिखा। उन्होंने कुछ दिलचस्प पाया:

इंसान स्मार्ट होते हैं। पहेली सुलझाते समय, हम शॉर्टकट देख सकते हैं। "ओह, मैं देख सकता हूँ कि उत्तर पहले से ही वहाँ है! मैं बाकी काम छोड़ देता हूँ।"
कंप्यूटर आज्ञाकारी लेकिन मूर्ख होता है। वह नियमों का सख्ती से पालन करता है। वह कोई शॉर्टकट नहीं लेता। वह हर एक कदम को पूरी तरह से करेगा, भले ही उत्तर स्पष्ट क्यों न हो।

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

प्रयोग: क्या यह काम कर गया?

उन्होंने अपने प्रोग्राम का परीक्षण हजारों रैंडम लॉजिक पजल्स पर किया।

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

यह क्यों मायने रखता है?

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

सारांश उपमा

कल्पना कीजिए कि आप भाषा A से भाषा B में एक संदेश का अनुवाद करने की कोशिश कर रहे हैं।

पुराना तरीका: आप शब्द-दर-शब्द अनुवाद करते हैं, हर एक शब्द के लिए डिक्शनरी चेक करते हैं।
नया तरीका: आप महसूस करते हैं कि भाषा A और भाषा B में एक विशिष्ट व्याकरण संरचना साझा है। आप A और B के अद्वितीय शब्दों को हटा देते हैं, जिससे केवल साझा व्याकरण बचता है। फिर आप केवल उस साझा व्याकरण का उपयोग करके संदेश का पुनर्निर्माण करते हैं।

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

यहाँ एडम ट्राइबस, कैरोलिना रोज़को और टोमाज़ स्कुरा के शोध पत्र "A Non-Binary Method for Finding Interpolants: Theory and Practice" का विस्तृत तकनीकी सारांश दिया गया है।

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

यह शोध पत्र शास्त्रीय प्रस्तावात्मक तर्क (classical propositional logic) में क्रेग इंटरपोलेशन (Craig Interpolation) की समस्या को संबोधित करता है। दो सूत्रों $A$ और $B$ के दिए जाने पर, जहाँ $A \to B$ एक वैध (tautology) है और वे कम से कम एक प्रस्तावात्मक चर (propositional variable) साझा करते हैं, लक्ष्य एक इंटरपुलेंट (interpolant) $C$ खोजना है ताकि:

$A \to C$ वैध हो।
$C \to B$ वैध हो।
$C$ में केवल वे ही प्रस्तावात्मक चर हों जो $A$ और $B$ दोनों में सामान्य (common) हैं।

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

2. कार्यप्रणाली (Methodology)

लेखक एक नवीन विधि प्रस्तावित करते हैं जो मानक प्रमाण प्रणालियों (proof systems) के बजाय रिफ्यूटेशन सिस्टम (refutation systems) पर आधारित है।

A. सैद्धांतिक आधार: रिफ्यूटेशन सिस्टम (Theoretical Foundation: Refutation Systems)

वैधता को सीधे सिद्ध करने के बजाय, यह विधि एक "दर्पण" (mirror) प्रणाली का उपयोग करती है जो अवैधता (non-validity/refutability) को सिद्ध करती है।

रिफ्यूटेशन एक्सिओम्स (Refutation Axioms): गैर-वैध सूत्र (विशेष रूप से रैंक 0 के क्लॉज़ल नॉर्मल फॉर्म)।
रिफ्यूटेशन रूल्स (Refutation Rules): वे नियम जो गैर-वैधता को बनाए रखते हैं। मुख्य तंत्र में एक जोड़ी पूरक लिटरल ( $l$ और $l^*$ ) को एक सूत्र से हटाना शामिल है।
मुख्य गुण (†): एक सूत्र $F$ वैध है यदि और केवल यदि इसके दोनों "शाखाएँ" $F_1$ और $F_2$ (जो $l, l^*$ के निष्कासन से प्राप्त होती हैं) वैध हैं। यह गुण इंटरपुलेंट्स को पुनरावर्ती (recursively) रूप से बनाने की अनुमति देता है।

B. इंटरपुलेंट खोजने की प्रक्रिया (The Interpolant-Finding Procedure)

एल्गोरिदम नॉर्मल फॉर्म ( $X \to Y$ , जहाँ $X$ CNF में है और $Y$ DNF में है) वाले सूत्रों पर कार्य करता है।

आधार मामला (Base Case - Rank 0): यदि $X$ $X$ और $Y$ $Y$ के बीच कोई पूरक लिटरल मौजूद नहीं है:
- यदि $X$ में विरोधाभास (empty clause) है, तो इंटरपुलेंट $\bot$ (False) है।
- यदि $Y$ में टॉटोलॉजी (complement में empty clause) है, तो इंटरपुलेंट $\top$ (True) है।
पुनरावर्ती चरण (Recursive Step - Rank > 0):
- $X \cup Y^*$ के अलग-अलग क्लॉज़ में मौजूद पूरक लिटरल $l, l^*$ की एक जोड़ी चुनें।
- $l$ और $l^*$ को हटाने के लिए रिफ्यूटेशन नियमों को लागू करके समस्या को दो उप-समस्याओं ( $G_1$ और $G_2$ ) में विभाजित करें।
- $I(G_1)$ और $I(G_2)$ के लिए इंटरपुलेंट खोजें।
- अंतिम इंटरपुलेंट $I(G)$ का निर्माण करें मूल सेटों में $l$ $l$ और $l^*$ $l^{*}$ की उपस्थिति के आधार पर:
  - यदि $l, l^*$ केवल $X$ में हैं: $I(G) = I(G_1) \land I(G_2)$ ।
  - यदि $l, l^*$ केवल $Y^*$ में हैं: $I(G) = I(G_1) \lor I(G_2)$ ।
  - यदि $l, l^*$ दोनों में हैं: $I(G) = (l \lor I(G_1)) \land (l^* \lor I(G_2))$ ।

C. कार्यान्वयन (Implementation)

लेखकों ने इस प्रक्रिया को एक पायथन स्क्रिप्ट (Python script) के रूप में लागू किया है।

डिज़ाइन: एक प्रूफ-ऑफ-कॉन्सेप्ट कार्यान्वयन जो बिना किसी मानवीय अनुकूलित शॉर्टकट (जैसे कि यदि कोई टॉटोलॉजी स्पष्ट है तो भी चरणों को छोड़ना नहीं) के सख्ती से सैद्धांतिक एल्गोरिदम का पालन करता है।
इनपुट हैंडलिंग: CNF/DNF में सूत्रों को स्वीकार करता है। स्क्रिप्ट पुनरावर्ती रूप से वेरिएबल एलिमिनेशन को संभालती है, जब तक कि बेस केस तक समस्या रूपांतरित न हो जाए।
सरलीकरण (Simplification): कच्चा आउटपुट जटिल हो सकता है (जैसे कि $\bot$ और $\top$ का अनावश्यक रूप से होना), लेकिन पेपर में उल्लेख है कि एक सरलीकरण फ़ंक्शन इन्हें मानक तार्किक रूपों में बदल सकता है।

3. मुख्य योगदान (Key Contributions)

नॉन-बाइनरी रेजोल्यूशन दृष्टिकोण: प्राथमिक योगदान एक इंटरपुलेंट खोज विधि है जो बाइनरी रेजोल्यूशन पर निर्भर नहीं करती है। इसके बजाय, यह नॉन-बाइनरी रेजोल्यूशन की अवधारणा का उपयोग करती है जो रिफ्यूटेशन सिस्टम से प्राप्त है, जिससे लिटरल जोड़ियों को एक ही चरण में हटाने की अनुमति मिलती है, जिसे अन्य सिस्टमों में कई बाइनरी रेजोल्यूशन चरणों की आवश्यकता हो सकती है।
रचनात्मक प्रमाण (Constructive Proof): पेपर विस्तारित इंटरपोलेशन प्रमेय (Extended Interpolation Theorem) का एक नया, सरल और रचनात्मक प्रमाण प्रदान करता है। यह प्रमाण सीधे एक एल्गोरिदम में अनुवाद योग्य है।
व्यावहारिक कार्यान्वयन: लेखक एक कार्यशील पायथन कार्यान्वयन प्रदान करते हैं और प्रदर्शन परीक्षण करते हैं, जिससे यह प्रदर्शित होता है कि सैद्धांतिक दृष्टिकोण व्यावहारिक अनुप्रयोग के लिए व्यवहार्य है।
दक्षता क्षमता (Efficiency Potential): लेखक तर्क देते हैं कि बाइनरी रेजोल्यूशन से बचकर, यह विधि इंटरपुलेंट्स को कम चरणों में उत्पन्न कर सकती है। वे एक उदाहरण उद्धृत करते हैं जहाँ उनकी विधि को 2 चरणों की आवश्यकता होती है, जबकि उसी समस्या के लिए HKP-सिस्टम को 5 चरणों की आवश्यकता होती है।

4. प्रयोगात्मक परिणाम (Experimental Results)

लेखकों ने प्रदर्शन का परीक्षण करने के लिए दो प्रकार के प्रयोग किए:

प्रयोग 1 (सीमित चर):
- 4 चरों तक के 100,000 सूत्र उत्पन्न किए गए।
- परिणाम: छोटे सूत्रों के लिए औसत निष्पादन समय 0.0032 सेकंड और बड़े सूत्रों के लिए 0.011 सेकंड था।
- अवलोकन: इनपुट सूत्र ( $X \to Y$ ) के आकार और निष्पादन समय के बीच एक रैखिक संबंध देखा गया।
प्रयोग 2 (विस्तारित चर):
- 10 चरों तक के 1,000 सूत्रों पर परीक्षण किया गया।
- परिणाम: रैखिक प्रदर्शन रुझान बना रहा।
- डेटा: परिणामी इंटरपुलेंट्स का आकार इनपुट आकार के साथ सह-संबंधित था, और निष्पादन समय मिलीसेकंड में कम रहा।
तुलना: D'Silva [2010] के एक विशिष्ट बेंचमार्क मामले में, प्रस्तावित विधि ने समस्या को 2 चरणों में हल किया, जबकि HKP-सिस्टम को 5 चरणों की आवश्यकता थी।

5. महत्व और भविष्य का कार्य (Significance and Future Work)

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

संक्षेप में, यह शोध पत्र मानक इंटरपोलेशन विधियों के एक सैद्धांतिक रूप से सुदृढ़ और व्यावहारिक रूप से व्यवहार्य विकल्प को प्रस्तुत करता है, जो नॉन-बाइनरी रेजोल्यूशन के माध्यम से अधिक दक्षता प्राप्त करने के लिए रिफ्यूटेशन सिस्टम का लाभ उठाता है।