प्रॉपर्टी टेस्टिंग

For the software testing technique, see Software testing § Property testing.

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

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

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

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

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

औपचारिक रूप से, निर्णय समस्या L के लिए क्वेरी जटिलता q(n) और निकटता पैरामीटर ε के साथ एक संपत्ति परीक्षण एल्गोरिदम एक यादृच्छिक एल्गोरिदम है, जो इनपुट x पर है ' ('एल का एक उदाहरण) x के लिए अधिकतम q(|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}$ किनारे और पहले ग्राफ़ से दूसरे तक पहुँचें। ग्राफ़ के उचित प्रतिनिधित्व के तहत, यह पहले की हैमिंग दूरी परिभाषा (संभवतः स्थिरांक में परिवर्तन तक) के बराबर है।

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

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

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

ग्राफ़ संपत्ति परीक्षण का क्षेत्र सबसे पहले गोल्डरिच, गोल्डवेसर और रॉन द्वारा पेश किया गया था। 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}$ किनारों.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

</ब्लॉककोट>

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

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

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

</ब्लॉककोट>

<ब्लॉककोट> उदाहरण (के-रंग योग्यता परीक्षण एल्गोरिदम)।

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

</ब्लॉककोट>