संपत्ति परीक्षण

For सॉफ्टवेयर परीक्षण तकनीक, see सॉफ्टवेयर परीक्षण विशेशता परीक्षण.

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

उदाहरण के लिए, निम्नलिखित संकेत समस्या एल्गोरिथ्म को स्वीकार करती है जिसकी क्वेरी जटिलता उदाहरण के आकार से स्वतंत्र होते है (स्वेच्छ स्थिरांक ε > 0 के लिए):

"n शीर्षों पर एक ग्राफ G दिया गया है, तय करें कि क्या G द्विदलीय ग्राफ है,या G को अधिक से अधिक स्वेच्छ स्थिरांक उपसमुच्चय को हटाने के बाद भी द्विदलीय नहीं बनाया जा सकता है $\epsilon {\tbinom {n}{2}}$ G के किनारों पर होता है

संपत्ति परीक्षण एल्गोरिदम संभाव्य रूप से जांचने योग्य प्रमाणों की परिभाषा के केंद्र में हैं, क्योंकि संभाव्य रूप से जांचने योग्य प्रमाण अनिवार्य रूप से एक प्रमाण है जिसे संपत्ति परीक्षण एल्गोरिदम द्वारा सत्यापित किया जा सकता है।

परिभाषा और प्रकार

औपचारिक रूप से, निर्णय समस्या L के लिए क्वेरी जटिलता q(n) और निकटता पैरामीटर ε के साथ एक संपत्ति परीक्षण एल्गोरिदम एक यादृच्छिक एल्गोरिदम होता है, जो इनपुट x (L का एक उदाहरण) पर अधिकतम q(|x|) क्वेरी x बनाता है और इस प्रकार व्यवहार करता है:

• यदि x L में है, तो एल्गोरिदम x को कम से कम ⅔ संभावना के साथ स्वीकार करता है।
• यदि x L से ε-दूर है, तो एल्गोरिदम कम से कम ⅔ संभावना के साथ x को अस्वीकार कर देता है।

यहां, "x L से ε-दूर है" , इसका का अर्थ है कि x और L में किसी भी तंता के बीच हैमिंग दूरी कम से कम ε|x| होती है।

एक संपत्ति परीक्षण एल्गोरिदम को एकतरफा त्रुटि कहा जाता है यदि यह मजबूत स्थिति को तुष्ट करता है कि उदाहरणों x ∈ L के लिए स्वीकार्य संभावना ⅔ के अतिरिक्त 1 होता है।

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

विशेषताएँ एवं सीमाएँ

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

अन्य जटिलता-सैद्धांतिक समायोजन के विपरीत, संपत्ति परीक्षण एल्गोरिदम की स्पर्शोन्मुख क्वेरी जटिलता उदाहरणों के प्रतिनिधित्व से नाटकीय रूप से प्रभावित होती है। उदाहरण के लिए, जब ε = 0.01, घने ग्राफ़ (जो उनके आसन्न मैट्रिक्स द्वारा दर्शाए जाते हैं) की द्विपक्षीयता के परीक्षण की समस्या निरंतर क्वेरी जटिलता के एल्गोरिदम को स्वीकार करती है। इसके विपरीत, n शीर्षों पर विरल ग्राफ़ (जो उनकी आसन्न सूची द्वारा दर्शाए जाते हैं) को क्वेरी जटिलता के संपत्ति परीक्षण एल्गोरिदम की आवश्यकता होती है $\Omega ({\sqrt {n}})$.

संपत्ति परीक्षण एल्गोरिदम की क्वेरी जटिलता बढ़ती है क्योंकि निकटता पैरामीटर ε सभी गैर-तुच्छ गुणों के लिए छोटा हो जाता है। ε पर यह निर्भरता आवश्यक है क्योंकि इनपुट में ε से कम प्रतीकों के परिवर्तन को O(1/ε) से कम प्रश्नों का उपयोग करके निरंतर संभावना के साथ पता नहीं लगाया जा सकता है। घने ग्राफ़ के कई रोचक गुणों का परीक्षण क्वेरी जटिलता का उपयोग करके किया जा सकता है जो केवल ε पर निर्भर करता है न कि ग्राफ़ आकार n पर होता है। चूँकि, ε के फ़ंक्शन के रूप में क्वेरी जटिलता बहुत तेज़ी से बढ़ सकती है। उदाहरण के लिए, लंबे समय तक यह परीक्षण करने के लिए सबसे प्रसिद्ध एल्गोरिदम था कि क्या ग्राफ में कोई त्रिकोण नहीं है, इसमें एक क्वेरी जटिलता थी जो पॉली (1/ε) का का टावर फलन होता है, और केवल 2010 में इसे टावर फलन में सुधार किया गया है लॉग का(1/ε)। सीमा में इस भारी वृद्धि का एक कारण यह है कि ग्राफ़ के संपत्ति परीक्षण के कई सकारात्मक परिणाम स्ज़ेमेरीडी नियमितता लेम्मा का उपयोग करके स्थापित किए जाते हैं, जिसके निष्कर्षों में टावर-प्रकार की सीमाएं भी होती हैं। सज़ेमेरीडी नियमितता लेम्मा और संबंधित ग्राफ़ निष्कासन लेम्मा के साथ संपत्ति परीक्षण का संबंध नीचे विस्तार से बताया गया है।

ग्राफ़ गुणों का परीक्षण

n शीर्षों वाले ग्राफ G के लिए, हम जिस दूरी की धारणा का उपयोग करेंगे वह संपादन दूरी है। अर्थात , हम कहते हैं कि दो ग्राफ़ के बीच की दूरी सबसे छोटी ε है, जिसे कोई जोड़ और/या हटा सकता है $\varepsilon n^{2}$ किनारे और पहले ग्राफ़ से दूसरे तक पहुँचें। ग्राफ़ के उचित प्रतिनिधित्व के अनुसार , यह पहले की हैमिंग दूरी परिभाषा (संभवतः स्थिरांक में परिवर्तन तक) के बराबर है।

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

हम केवल उन ग्राफों के बीच अंतर कर सकते हैं जो P को तुष्ट करते हैं बनाम जो P से दूर हैं, इसके विपरीत जो तुष्ट करते हैं बनाम जो P को तुष्ट नहीं करते हैं। बाद के स्थिति में, दो ग्राफ़ पर विचार करें: G तुष्ट करने वाला P और एच केवल कुछ किनारों को बदलकर P को तुष्ट नहीं कर रहा है। एक उदाहरण एच के साथ त्रिकोण-मुक्तता का परीक्षण कर रहा है, जिसमें बिल्कुल एक त्रिकोण है और G में इनमें से एक किनारा हटा दिया गया है। फिर, परीक्षक उन्हें तब तक अलग नहीं बता सकता जब तक कि वह हर किनारे पर सवाल न उठा ले, जो वह नहीं कर सकता है।

संक्षिप्त इतिहास

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

तब से, कई संबंधित खोजें की गई हैं

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

वंशानुगत ग्राफ गुणों का परीक्षण

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

'प्रमेय (अलोन और शापिरा 2008)।' प्रत्येक वंशानुगत ग्राफ़ संपत्ति एकतरफा त्रुटि के साथ परीक्षण योग्य है।

प्रमाण प्रेरित सबग्राफ के अनंत परिवारों के लिए ग्राफ हटाने वाली लेम्मा के एक संस्करण पर निर्भर करता है। हम यहां प्रमेय को बिना प्रमाण के पुन: प्रस्तुत कर रहे हैं। विशेष रूप से, उस स्थिरांक पर ध्यान दें $h_{0}$ नमूनों के आकार के अनुसार स्वाभाविक रूप से सामने आते हैं। इसके अतिरिक्त, इस नियमितता दृष्टिकोण का उपयोग करने वाली क्वेरी जटिलता स्ज़ेमेरीडी नियमितता लेम्मा में टेट्रेशन के कारण बड़ी है।

प्रमेय (अनंत ग्राफ निष्कासन प्रमेयिका)। ग्राफ़ के प्रत्येक (संभवतः अनंत) सेट के लिए ${\mathcal {H}}$ और $\varepsilon >0$, वहां सम्मलित होता है $h_{0}$ और $\delta >0$ जिससे यदि $G$ एक $n$-से कम के साथ वर्टेक्स ग्राफ $\delta n^{v(H)}$ की प्रतियाँ $H$ के लिए $H\in {\mathcal {H}}$ अधिक से अधिक के साथ $h_{0}$ शीर्ष, तो $G$ प्रेरित किया जा सकता है ${\mathcal {H}}$-से कम जोड़ने/हटाने से मुफ़्त $\varepsilon n^{2}$ किनारों पर होता है।

अनभिज्ञ परीक्षक

अनौपचारिक रूप से, एक अनभिज्ञ परीक्षक इनपुट के आकार से अनभिज्ञ होता है। ग्राफ प्रॉपर्टी P के लिए, यह एल्गोरिदम है जो इनपुट के रूप में पैरामीटर ε और ग्राफ G लेता है, और फिर निकटता पैरामीटर ε के साथ प्रॉपर्टी P के लिए G पर प्रॉपर्टी परीक्षण एल्गोरिदम के रूप में चलता है जो G के लिए बिल्कुल q (ε) क्वेरी बनाता है।

'परिभाषा।' एक विस्मृति परीक्षक एक एल्गोरिथ्म है जो इनपुट के रूप में एक पैरामीटर ε लेता है। यह एक पूर्णांक q(ε) की गणना करता है और फिर यादृच्छिक रूप से समान रूप से चुने गए G से बिल्कुल q(ε) शीर्षों पर एक प्रेरित सबग्राफ H के लिए दैवज्ञ से पूछता है।फिर यह ε और H के अनुसार (संभवतः यादृच्छिक रूप से) स्वीकार या अस्वीकार करता है। हम कहते हैं कि यह संपत्ति P के लिए परीक्षण करता है यदि यह G के लिए कम से कम ⅔ संभावना के साथ स्वीकार करता है जिसके पास संपत्ति P है, और कम से कम ⅔ या G यानी ε के साथ अस्वीकार करता है -संपत्ति से दूर P होता हैं।

महत्वपूर्ण रूप से, परीक्षक द्वारा किए गए प्रश्नों की संख्या एक स्थिरांक है जो केवल ε पर निर्भर करती है, न कि इनपुट ग्राफ G के आकार पर होता है । संपत्ति परीक्षण एल्गोरिदम के साथ पूर्ण सादृश्य में, हम एक तरफा त्रुटि वाले परीक्षकों के बारे में बात कर सकते हैं।

अर्ध-वंशानुगत ग्राफ गुणों का परीक्षण

हम निश्चित रूप से कुछ ग्राफ गुण बना सकते हैं जहां इसके लिए एक परीक्षक को शीर्षों की संख्या तक पहुंच होनी चाहिए। यहाँ एक उदाहरण है

उदाहरण। एक ग्राफ G संपत्ति P को तुष्ट करता है यदि यह सम संख्या में शीर्षों के साथ द्विदलीय है या विषम संख्या में शीर्षों के साथ पूर्ण होता है।

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

परिभाषा। एक ग्राफ गुण H अर्ध-वंशानुगत है यदि वंशानुगत ग्राफ गुण H मे सम्मलित होता है जैसे कि P को तुष्ट करने वाला कोई भी ग्राफ H को तुष्ट करता है, और प्रत्येक के लिए $\varepsilon >0$ वहाँ है एक $M(\varepsilon )$ ऐसा कि आकार का हर ग्राफ़ कम से कम $M(\varepsilon )$ जो कि P को तुष्ट करने से ε-दूर है, इसमें एक प्रेरित सबग्राफ सम्मलित होता है जो H को तुष्ट नहीं करता है।

तुच्छ रूप से, वंशानुगत गुण भी अर्ध-वंशानुगत होते हैं। यह विशेषीकरण वर्णन आंशिक रूप से उपरोक्त अन्य अलोन और शापिरा प्रमेय के विपरीत उत्तर देता है: जिन गुणों का परीक्षण करना आसान है (एकतरफा त्रुटि वाले अनभिज्ञ परीक्षक होना) वे लगभग वंशानुगत हैं। उसी पेपर में उन्होंने दिखाया

प्रमेय (अलोन और शापिरा 2008)। एक ग्राफ प्रॉपर्टी P में एक तरफा त्रुटि परीक्षक है, यदि और केवल यदि P अर्ध-वंशानुगत है।

उदाहरण: कुछ ग्राफ़ गुणों का परीक्षण

इस खंड में, हम त्रिकोण-मुक्तता, द्विदलीयता और के-रंग योग्यता के लिए एक तरफा त्रुटि के साथ कुछ प्राकृतिक विस्मृति परीक्षण एल्गोरिदम देंगे। वे इस अर्थ में स्वाभाविक हैं कि हम G के शीर्षों के कुछ सबसेट हमारे पास एक तरफा त्रुटि है क्योंकि ये गुण वास्तव में वंशानुगत होता हैं: यदि G संपत्ति को तुष्ट करता है, तो एक्स द्वारा फैलाए गए प्रेरित सबग्राफ को भी तुष्ट करना चाहिए, इसलिए हमारा परीक्षक सदैव स्वीकार करता है।

त्रिकोण-मुक्ति के लिए, परीक्षक त्रिकोण हटाने वाली लेम्मा का एक अनुप्रयोग है। विशेष रूप से, यह हमें बताता है कि यदि ग्राफ G त्रिकोण-मुक्त होने से ε-दूर है, तो एक (गणना योग्य) स्थिरांक होता है $\delta =\delta (\varepsilon )$ जिससे G के पास कम से कम हो $\delta n^{3}$ त्रिभुज होता है।

उदाहरण (त्रिकोण-मुक्तता परीक्षण एल्गोरिदम)।

1. दिए गए ग्राफ़ G में से एक यादृच्छिक सेट X चुनें $q(\varepsilon )=1/\delta$ शीर्षों के त्रिगुण स्वतंत्र रूप से यादृच्छिक रूप से, जहां δ ऊपर जैसा है।
2. X में शीर्षों के प्रत्येक त्रिक के लिए, पूछें कि क्या शीर्षों के सभी तीन युग्मित G में आसन्न होते हैं।
3. यदि शीर्षों का कोई त्रिगुण त्रिभुज उत्पन्न नहीं करता है तो एल्गोरिदम स्वीकार करता है, और अन्यथा अस्वीकार कर देता है।

द्विपक्षीयता और के-रंग योग्यता के लिए, निम्नलिखित परीक्षकों के लिए त्रुटि संभावना पर वांछित ऊपरी सीमा होने दें। ध्यान दें, क्वेरी जटिलता को रनिंग टाइम के साथ भ्रमित नहीं किया जाना चाहिए। प्रेरित सबग्राफ पर गुण का परीक्षण करने के लिए बहुपद समय निर्णय एल्गोरिदम की कमी के कारण उत्तरार्द्ध अधिकांशतः घातांकीय होता है (जैसा कि दोनों का स्थिति है)। इसके अतिरिक्त हम क्रूर-बल खोज द्वारा जाँच करते हैं।

उदाहरण (द्विपक्षीय परीक्षण एल्गोरिदम)।

1. दिए गए ग्राफ G में से एक यादृच्छिक सेट X चुनें $q(\varepsilon )=O(\log(1/(\varepsilon \delta ))/\varepsilon ^{2})$ शीर्ष।
2. X में शीर्षों के प्रत्येक जोड़े के लिए, पूछें कि क्या वे G में आसन्न होता हैं।
3. यदि X पर G का प्रेरित उपसमूह द्विदलीय है तो यह स्वीकार करता है और अन्यथा अस्वीकार कर देता है।

उदाहरण (k-रंग योग्यता परीक्षण एल्गोरिदम)।

1. दिए गए ग्राफ़ G में से एक यादृच्छिक सेट X चुनें $q(\varepsilon )=O(k^{4}\log ^{2}(k/\delta )/\varepsilon ^{3})$ शीर्ष पर होता है।
2. X में शीर्षों के प्रत्येक जोड़े के लिए, पूछें कि क्या वे G में आसन्न होता हैं।
3. यदि X पर G का प्रेरित सबग्राफ k-रंग योग्य है तो यह स्वीकार करता है और अन्यथा अस्वीकार कर देता है।