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

"औसत.पी" redirects here. For अन्य उपयोग, see औसत पी (असंबद्धता).

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

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

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

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

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|. दूसरे शब्दों में, एक कलन विधि {{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.