एवरेज-केस कम्प्लेक्सिटी

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

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

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

इतिहास और पृष्ठभूमि

1950 के दशक में कम्प्यूटेशनल दक्षता की आधुनिक धारणाएँ विकसित होने के बाद से कलन विधि के औसत-केस प्रदर्शन का अध्ययन किया गया है। इस आरंभिक कार्य का अधिकांश भाग उन समस्याओं पर केंद्रित था जिनके लिए सबसे खराब स्थिति वाले बहुपद समय कलन विधि पहले से ही ज्ञात थे।1973 में, डोनाल्ड नुथ ने आर्ट ऑफ़ कंप्यूटर प्रोग्रामिंग का खंड 3 प्रकाशित किया, जो सॉर्टिंग और मीडियन-फाइंडिंग जैसी सबसे खराब स्थिति वाले बहुपद समय में हल करने योग्य समस्याओं के लिए कलन विधि के औसत-केस प्रदर्शन का व्यापक सर्वेक्षण करता है।

NP-पूर्ण समस्याओं के लिए एक कुशल कलन विधि को सामान्यतः ऐसे कलन विधि के रूप में जाना जाता है जो सभी इनपुट के लिए बहुपद समय में चलता है; यह सबसे खराब स्थिति में कुशल सम्मिश्रता की आवश्यकता के बराबर है। हालाँकि, एक एल्गोरिथ्म जो "छोटी" संख्या में इनपुट पर अक्षम है, वह अभी भी व्यवहार में आने वाले "अधिकांश" इनपुट के लिए कुशल हो सकता है। इस प्रकार, इन कलन विधि के गुणों का अध्ययन करना वांछनीय है जहां एवरेज-केस कम्प्लेक्सिटी सबसे खराब-कारक की सम्मिश्रता से भिन्न हो सकती है और दोनों को संबंधित करने के तरीकों को ढूंढना है।

एवरेज-केस कम्प्लेक्सिटी की मौलिक धारणाएं 1986 में लियोनिद लेविन द्वारा विकसित की गईं जब उन्होंने एक पेज का पेपर प्रकाशित किया। NP के औसत-केस एनालॉग, distNP के लिए एक संपूर्ण समस्या का उदाहरण देते हुए औसत-केस सम्मिश्रता और पूर्णता को परिभाषित करना है।

परिभाषाएँ

कुशल एवरेज-केस कम्प्लेक्सिटी

पहला कार्य यह स्पष्ट रूप से परिभाषित करना है कि कलन विधि का क्या मतलब है जो "औसतन" कुशल है। प्रारंभिक प्रयास कुशल औसत-केस कलन विधि को परिभाषित कर सकता है जो सभी संभावित इनपुट पर अपेक्षित बहुपद समय में चलता है। ऐसी परिभाषा में कई कमियाँ हैं; विशेष रूप से, यह कम्प्यूटेशनल मॉडल में परिवर्तन के लिए मजबूत नहीं है। उदाहरण के लिए, मान लीजिए कि कलन विधि A इनपुट x पर समय t_A(x) में चलता है और कलन विधि B इनपुट x पर समय t_A(x)² में चलता है; अर्थात्, B, A की तुलना में चतुष्कोणीय रूप से धीमा है। सहज रूप से, औसत-कारक की दक्षता की किसी भी परिभाषा में इस विचार को सम्मिलित किया जाना चाहिए कि A औसत पर कुशल है यदि और केवल यदि B औसत पर कुशल है। हालाँकि, मान लीजिए कि इनपुट लंबाई n के साथ स्ट्रिंग के समान वितरण से यादृच्छिक रूप से निकाले जाते हैं, और A स्ट्रिंग 1ⁿ को छोड़कर सभी इनपुट पर समय n² में चलता है जिसके लिए A को 2ⁿ समय लगता है। तब यह आसानी से जांचा जा सकता है कि A का अपेक्षित रनिंग समय बहुपद है लेकिन B का पेक्षित चलने का समय घातीय है।

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

$\Pr _{x\in _{R}D_{n}}\left[t_{A}(x)\geq t\right]\leq {\frac {p(n)}{t^{\epsilon }}}$

हरएक के लिए n, t > 0 और बहुपद p, जहाँ t_A(x) एल्गोरिथम के चलने के समय को दर्शाता है A इनपुट पर x, और ε धनात्मक स्थिरांक मान है. वैकल्पिक रूप से, इसे इस प्रकार लिखा जा सकता है

$E_{x\in _{R}D_{n}}\left[{\frac {t_{A}(x)^{\epsilon }}{n}}\right]\leq C$

कुछ स्थिरांक C और ε के लिए, जहां n = |x| दूसरे शब्दों में, कलन विधि A में एवरेज-केस कम्प्लेक्सिटी अच्छी होती है, यदि t_A(n) चरणों के लिए चलने के बाद, A कुछ ε, c > 0 के लिए लंबाई n के इनपुट के n^c/(t_A(n))^ε अंश को छोड़कर सभी को हल कर सकता है।

वितरण संबंधी समस्या

अगला कदम एक विशेष समस्या के लिए "औसत" इनपुट को परिभाषित करना है। यह प्रत्येक समस्या के इनपुट को एक विशेष संभावना वितरण के साथ जोड़कर हासिल किया जाता है। अर्थात्, औसत-कारक की समस्या में एक भाषा सम्मिलित होती है L और संबद्ध संभाव्यता D वितरण (L, D) जो जोड़ी बनाता है . वितरण के दो सबसे सामान्य वर्ग जिनकी अनुमति है वे हैं:

1. बहुपद-समय गणना योग्य वितरण (P-कंप्यूटेबल): ये ऐसे वितरण हैं जिनके लिए किसी दिए गए इनपुट x के संचयी घनत्व की गणना करना संभव है। अधिक औपचारिक रूप से, संभाव्यता वितरण μ और स्ट्रिंग x ∈ {0, 1}ⁿ को देखते हुए, बहुपद समय में मान $\mu (x)=\sum \limits _{y\in \{0,1\}^{n}:y\leq x}\Pr[y]$ की गणना करना संभव है। इसका तात्पर्य यह है कि Pr[x] की गणना बहुपद समय में भी की जा सकती है।
2. बहुपद-समय नमूना वितरण (P-नमूना): ये ऐसे वितरण हैं जिनसे बहुपद समय में यादृच्छिक नमूने निकालना संभव है।

ये दोनों सूत्रीकरण, समान होते हुए भी, समतुल्य नहीं हैं। यदि कोई वितरण P-गणना योग्य है तो यह भी P-नमूना योग्य है, लेकिन यदि P≠P^#P है तो इसका विपरीत सत्य नहीं है।

एवीजीपी और डिस्टएनपी

वितरण संबंधी समस्या (L, D) सम्मिश्रता वर्ग में है AvgP यदि इसके लिए एक कुशल औसत-केस L कलन विधि है, जैसा कि ऊपर परिभाषित किया गया है। वर्ग AvgP को कभी-कभी साहित्य में distP कहा जाता है।

वितरण संबंधी समस्या (L, D) सम्मिश्रता वर्ग distNP में है यदि L NP में है और D P-कंप्यूटेबल है। जब L NP में है और D P-नमूना योग्य है, (L, D) sampNP से संबंधित है।

साथ में, AvgP और distNP क्रमशः P और NP के औसत-केस एनालॉग्स को परिभाषित करते हैं।

वितरण संबंधी समस्याओं के बीच अपचयन

मान लीजिए (L,D) और (L′, D′) दो वितरण संबंधी समस्याएं हैं। (L, D) औसत कारक घटकर (L′, D′) हो जाता है (लिखित (L, D) ≤_AvgP (L′, D′))  यदि कोई फ़ंक्शन f है जो प्रत्येक n के लिए है, तो इनपुट x पर n और में समय बहुपद में गणना की जा सकती है

1. (सहीता) x ∈ L यदि और केवल यदि f(x) ∈ L′
2. (प्रभुत्व) बहुपद होते हैं p और m ऐसा कि, प्रत्येक n और y के लिए, $\sum \limits _{x:f(x)=y}D_{n}(x)\leq p(n)D'_{m(n)}(y)$

प्रभुत्व की स्थिति इस धारणा को लागू करती है कि यदि समस्या है (L, D) तो फिर औसत रूप से कठिन है (L′, D′) औसत रूप से भी कठिन है। सहज रूप से, कमी को किसी उदाहरण को हल करने का एक तरीका प्रदान करना चाहिए xसमस्या का L कंप्यूटिंग द्वारा f(x) और आउटपुट को कलन विधि को फीड करना जो हल करता है L'. प्रभुत्व की स्थिति के बिना, यह संभव नहीं हो सकता है क्योंकि कलन विधि जो हल करता है L बहुपद समय में औसतन कम संख्या में इनपुट पर सुपर-बहुपद समय लग सकता है f इन इनपुटों को बहुत बड़े सेट में मैप कर सकता है D' तो वह कलन विधि A' अब औसतन बहुपद समय में नहीं चलता। प्रभुत्व की स्थिति केवल ऐसे श्रृंखला को बहुपद रूप से घटित होने की अनुमति देती है जैसा कि प्रायः D' होता है।

डिस्टएनपी-पूर्ण समस्याएं

औसत-केस एनालॉग NP-सम्पूर्णता है distNP-सम्पूर्णता वितरण संबंधी समस्या (L′, D′) है distNP-पूर्ण करें यदि (L′, D′) में है distNP और प्रत्येक के लिए (L, D) में distNP, (L, D) औसत-कारक (L′, D′) को कम करने योग्य है।

A का एक उदाहरण distNP-पूर्ण समस्या बाउंडेड हॉल्टिंग समस्या है, BH, इस प्रकार परिभाषित:

$BH=\{(M,x,1^{t}):M{\text{ is a non-deterministic Turing machine that accepts }}x{\text{ in}}\leq t{\text{ steps}}\}$

अपने मूल पेपर में, लेविन ने वितरणात्मक टाइलिंग समस्या का उदाहरण दिखाया जो औसत-कारक है NP-पूरा। ज्ञात का सर्वेक्षण distNP-सम्पूर्ण समस्याएँ ऑनलाइन उपलब्ध है।

सक्रिय अनुसंधान के एक क्षेत्र में नया खोजना सम्मिलित है distNP-पूर्ण समस्याएँ। हालाँकि, गुरेविच के परिणाम के कारण ऐसी समस्याओं का पता लगाना जटिल हो सकता है जो दर्शाता है कि समतल वितरण के साथ कोई भी वितरण समस्या नहीं हो सकती है distNP-जब तक EXP|पूर्ण न हो जाएEXP = NEXP|NEXP. (समतल वितरण μ वह है जिसके लिए उपस्थित है ε > 0 ऐसा कि किसी के लिए भी x, μ(x) ≤ 2^−|x|ε.) लिव्ने के परिणाम से पता चलता है कि सब कुछ प्राकृतिक है NP-पूर्ण समस्याएँ हैं DistNP-पूर्ण संस्करण। हालाँकि, एक प्राकृतिक वितरणात्मक समस्या को खोजने का लक्ष्य यही है DistNP-अभी तक पूरा नहीं हो पाया है.

अनुप्रयोग

सॉर्टिंग कलन विधि

जैसा कि ऊपर उल्लेख किया गया है, एवरेज-केस कम्प्लेक्सिटी से संबंधित बहुत से प्रारंभिक कार्य उन समस्याओं पर केंद्रित थे जिनके लिए बहुपद-समय कलन विधि पहले से उपस्थित थे, जैसे कि सॉर्टिंग। उदाहरण के लिए, कई सॉर्टिंग कलन विधि जो यादृच्छिकता का उपयोग करते हैं, जैसे कि जल्दी से सुलझाएं, का चलने का समय सबसे खराब होता है O(n²), लेकिन औसत केस चलने का समय O(n log(n)), जहाँ n सॉर्ट किए जाने वाले इनपुट की लंबाई है।

क्रिप्टोग्राफी

अधिकांश समस्याओं के लिए, किसी समस्या के लिए कुशल कलन विधि खोजने के लिए औसत-कारक सम्मिश्रता विश्लेषण किया जाता है जिसे सबसे खराब स्थिति में कठिन माना जाता है। क्रिप्टोग्राफ़िक अनुप्रयोगों में, हालांकि, विपरीत सच है: सबसे खराब स्थिति की सम्मिश्रता अप्रासंगिक है; इसके बजाय हम यह गारंटी चाहते हैं कि क्रिप्टोग्राफ़िक योजना को "तोड़ने" वाले प्रत्येक कलन विधि की औसत-केस सम्मिश्रता अक्षम है। इस प्रकार, सभी सुरक्षित क्रिप्टोग्राफ़िक योजनाएँ एकपक्षीय फलन के अस्तित्व पर निर्भर करती हैं। हालाँकि एकपक्षीय फलन का अस्तित्व अभी भी एक रिक्त समस्या है, कई उम्मीदवार एकपक्षीय फलन पूर्णांक गुणनखंडन या असतत लॉग की गणना जैसी कठिन समस्याओं पर आधारित हैं। ध्यान दें कि उम्मीदवार के कार्य के लिए ऐसा होना वांछनीय नहीं है NP-पूर्ण क्योंकि यह केवल इस बात की गारंटी देगा कि सबसे खराब स्थिति में समस्या को हल करने के लिए कोई कुशल कलन विधि नहीं है; हम वास्तव में यह गारंटी चाहते हैं कि कोई भी कुशल कलन विधि यादृच्छिक इनपुट (यानी औसत कारक) पर समस्या का समाधान नहीं कर सकता है। वास्तव में, पूर्णांक गुणनखंडन NP ∩ औरcoNP|coNP असतत लॉग समस्याएँ दोनों ही हैं, और इसलिए NP-पूर्ण नहीं माना जाता है। तथ्य यह है कि संपूर्ण क्रिप्टोग्राफी औसत-कारक में कठिन समस्याओं के अस्तित्व पर आधारित है NP एवरेज-केस कम्प्लेक्सिटी का अध्ययन करने के लिए प्राथमिक प्रेरणाओं में से एक है।

अन्य परिणाम

1990 में, इम्पाग्लिआज़ो और लेविन ने दिखाया कि यदि किसी के लिए एक कुशल औसत-केस कलन विधि है distNP-समान वितरण के तहत पूर्ण समस्या, फिर प्रत्येक समस्या के लिए एक औसत-केस कलन विधि है NP किसी भी बहुपद-समय नमूना योग्य वितरण के तहत। इस सिद्धांत को प्राकृतिक वितरण संबंधी समस्याओं पर लागू करना एक उत्कृष्ट रिक्त प्रश्न बना हुआ है।

1992 में, बेन-डेविड एट अल। दिखाया कि यदि सभी भाषाओं में distNP उनके पास औसत पर अच्छे निर्णय कलन विधि हैं, उनके पास औसत पर अच्छे खोज कलन विधि भी हैं। इसके अलावा, वे दिखाते हैं कि यह निष्कर्ष एक कमजोर धारणा के अंतर्गत आता है: यदि प्रत्येक भाषा में NPसमान वितरण के संबंध में निर्णय कलन विधि के लिए औसत रूप से आसान है, फिर समान वितरण के संबंध में खोज कलन विधि के लिए भी यह औसत रूप से आसान है। इस प्रकार, क्रिप्टोग्राफ़िक एकपक्षीय फलन केवल तभी उपस्थित हो सकते हैं जब distNP वहाँ हों समान वितरण पर समस्याएं जो निर्णय कलन विधि के लिए औसतन कठिन हैं।

1993 में, फेगेनबाम और फ़ोर्टनो ने दिखाया कि गैर-अनुकूली यादृच्छिक अपचयन के तहत, यह सिद्ध करना संभव नहीं है कि एक औसतन अच्छा कलन विधि का अस्तित्व distNP-समान वितरण के तहत पूर्ण समस्या का तात्पर्य सभी समस्याओं के लिए सबसे खराब स्थिति वाले कुशल कलन विधि के अस्तित्व से है NP. 2003 में, बोगदानोव और ट्रेविसन ने इस परिणाम को मनमाने ढंग से गैर-अनुकूली अपचयन के रूप में सामान्यीकृत किया। इन परिणामों से पता चलता है कि यह संभावना नहीं है कि अपचयन के माध्यम से एवरेज-केस कम्प्लेक्सिटी और सबसे खराब-कारक की सम्मिश्रता के बीच कोई संबंध बनाया जा सकता है।

यह भी देखें

• कलन विधि का संभाव्य विश्लेषण
• NP-पूर्ण समस्याएं
• सबसे खराब स्थिति सम्मिश्रता
• परिशोधन विश्लेषण
• सबसे अच्छा, सबसे खराब और औसत कारक
• कलन विधि का संभाव्य विश्लेषण

अग्रिम पठन

The literature of average case complexity includes the following work:

• Franco, John (1986), "On the probabilistic performance of algorithms for the satisfiability problem", Information Processing Letters, 23 (2): 103–106, doi:10.1016/0020-0190(86)90051-7.
• Levin, Leonid (1986), "Average case complete problems", SIAM Journal on Computing, 15 (1): 285–286, doi:10.1137/0215020.
• Flajolet, Philippe; Vitter, J. S. (August 1987), Average-case analysis of algorithms and data structures, Tech. Report, Institut National de Recherche en Informatique et en Automatique, B.P. 105-78153 Le Chesnay Cedex France.
• Gurevich, Yuri; Shelah, Saharon (1987), "Expected computation time for Hamiltonian path problem", SIAM Journal on Computing, 16 (3): 486–502, CiteSeerX 10.1.1.359.8982, doi:10.1137/0216034.
• Ben-David, Shai; Chor, Benny; Goldreich, Oded; Luby, Michael (1989), "On the theory of average case complexity", Proc. 21st Annual Symposium on Theory of Computing, Association for Computing Machinery, pp. 204–216.
• Gurevich, Yuri (1991), "Average case completeness", Journal of Computer and System Sciences, 42 (3): 346–398, doi:10.1016/0022-0000(91)90007-R, hdl:2027.42/29307. See also 1989 draft.
• Selman, B.; Mitchell, D.; Levesque, H. (1992), "Hard and easy distributions of SAT problems", Proc. 10th National Conference on Artificial Intelligence, pp. 459–465.
• Schuler, Rainer; Yamakami, Tomoyuki (1992), "Structural average case complexity", Proc. Foundations of Software Technology and Theoretical Computer Science, Lecture Notes in Computer Science, vol. 652, Springer-Verlag, pp. 128–139.
• Reischuk, Rüdiger; Schindelhauer, Christian (1993), "Precise average case complexity", Proc. 10th Annual Symposium on Theoretical Aspects of Computer Science, pp. 650–661.
• Venkatesan, R.; Rajagopalan, S. (1992), "Average case intractability of matrix and Diophantine problems", Proc. 24th Annual Symposium on Theory of Computing, Association for Computing Machinery, pp. 632–642.
• Cox, Jim; Ericson, Lars; Mishra, Bud (1995), The average case complexity of multilevel syllogistic (PDF), Technical Report TR1995-711, New York University Computer Science Department.
• Impagliazzo, Russell (April 17, 1995), A personal view of average-case complexity, University of California, San Diego.
• Paul E. Black, "Θ", in Dictionary of Algorithms and Data Structures[online]Paul E. Black, ed., U.S. National Institute of Standards and Technology. 17 December 2004.Retrieved Feb. 20/09.
• Christos Papadimitriou (1994). Computational Complexity. Addison-Wesley.