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

"AvgP" redirects here. For other uses, see avgp (disambiguation).

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

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

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

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

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

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

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

परिभाषाएँ

कुशल औसत-मामले की जटिलता

पहला कार्य सटीक रूप से परिभाषित करना है कि एक एल्गोरिदम का क्या मतलब है जो औसतन कुशल है। एक प्रारंभिक प्रयास एक कुशल औसत-केस एल्गोरिदम को परिभाषित कर सकता है जो सभी संभावित इनपुट पर अपेक्षित बहुपद समय में चलता है। ऐसी परिभाषा में विभिन्न कमियाँ हैं; विशेष रूप से, यह कम्प्यूटेशनल मॉडल में बदलाव के लिए मजबूत नहीं है। उदाहरण के लिए, मान लीजिए एल्गोरिथ्म Aसमय पर चलता है t_A(x) इनपुट पर x और एल्गोरिदम Bसमय पर चलता है t_A(x)² इनपुट पर x; वह है, B की तुलना में चतुष्कोणीय रूप से धीमा है A. सहज रूप से, औसत-मामले दक्षता की किसी भी परिभाषा में इस विचार को शामिल किया जाना चाहिए A औसत पर कुशल है यदि और केवल यदि B औसत रूप से कुशल है. हालाँकि, मान लीजिए कि इनपुट लंबाई के साथ स्ट्रिंग के समान वितरण से यादृच्छिक रूप से लिए गए हैं n, ओर वो Aसमय पर चलता है n² स्ट्रिंग को छोड़कर सभी इनपुट पर 1ⁿ जिसके लिए 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|. दूसरे शब्दों में, एक एल्गोरिदम {{mvar|A}यदि, दौड़ने के बाद, } में औसत-मामले की जटिलता अच्छी है t_A(n) कदम, Aए को छोड़कर सभी को हल कर सकता है n^c/(t_A(n))^ε लंबाई के इनपुट का अंश n, कुछ के लिए ε, c > 0.

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

अगला कदम किसी विशेष समस्या के औसत इनपुट को परिभाषित करना है। यह प्रत्येक समस्या के इनपुट को एक विशेष संभाव्यता वितरण के साथ जोड़कर प्राप्त किया जाता है। अर्थात्, एक औसत-मामले की समस्या में एक भाषा शामिल होती है 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^#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′).

ए का एक उदाहरण 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 में, बोगदानोव और ट्रेविसन ने इस परिणाम को मनमाने ढंग से गैर-अनुकूली कटौती के रूप में सामान्यीकृत किया। इन परिणामों से पता चलता है कि यह संभावना नहीं है कि कटौती के माध्यम से औसत-मामले की जटिलता और सबसे खराब-मामले की जटिलता के बीच कोई संबंध बनाया जा सकता है।

यह भी देखें

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

अग्रिम पठन

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.