एवरेज-केस कम्प्लेक्सिटी: Difference between revisions

Revision as of 10:56, 11 July 2023

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

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

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

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

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

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

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

परिभाषाएँ

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

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

औसत-केस दक्षता की अधिक मजबूत परिभाषा बनाने के लिए, कलन विधि की अनुमति देना समझ में आता है $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$ , और $ε$ धनात्मक स्थिरांक मान है.^[6] वैकल्पिक रूप से, इसे इस प्रकार लिखा जा सकता है

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

कुछ स्थिरांक $C$ और $ε$ के लिए, जहां $n = | x |$ ^[7] दूसरे शब्दों में, कलन विधि $A$ में औसत-कारक की जटिलता अच्छी होती है, यदि $t A (n)$ चरणों के लिए चलने के बाद, A कुछ $ε, c > 0$ के लिए लंबाई $n$ के इनपुट के $.mw-parser-output .sfrac{white-space:nowrap}.mw-parser-output .sfrac.tion,.mw-parser-output .sfrac .tion{display:inline-block;vertical-align:-0.5em;font-size:85%;text-align:center}.mw-parser-output .sfrac .num,.mw-parser-output .sfrac .den{display:block;line-height:1em;margin:0 0.1em}.mw-parser-output .sfrac .den{border-top:1px solid}.mw-parser-output .sr-only{border:0;clip:rect(0,0,0,0);height:1px;margin:-1px;overflow:hidden;padding:0;position:absolute;width:1px}nc/(tA(n))ε$ अंश को छोड़कर सभी को हल कर सकता है।^[3]

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

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

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

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

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

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

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

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

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

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

(सहीता) $x \in L$ यदि और केवल यदि $f (x) \in L'$
(प्रभुत्व) बहुपद होते हैं $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'$ होता है।^[6]

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

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

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}}\}$ ^[7]

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

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

अनुप्रयोग

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

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

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

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

अन्य परिणाम

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

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

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

यह भी देखें

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

संदर्भ

↑ O. Goldreich and S. Vadhan, Special issue on worst-case versus average-case complexity, Comput. Complex. 16, 325–330, 2007.
↑ ^2.0 ^2.1 Cormen, Thomas H.; Leiserson, Charles E., Rivest, Ronald L., Stein, Clifford (2009) [1990]. Introduction to Algorithms (3rd ed.). MIT Press and McGraw-Hill. ISBN 0-262-03384-4.
↑ ^3.0 ^3.1 ^3.2 ^3.3 ^3.4 ^3.5 A. Bogdanov and L. Trevisan, "Average-Case Complexity," Foundations and Trends in Theoretical Computer Science, Vol. 2, No 1 (2006) 1–106.
↑ D. Knuth, The Art of Computer Programming. Vol. 3, Addison-Wesley, 1973.
↑ ^5.0 ^5.1 L. Levin, "Average case complete problems," SIAM Journal on Computing, vol. 15, no. 1, pp. 285–286, 1986.
↑ ^6.0 ^6.1 ^6.2 J. Wang, "Average-case computational complexity theory," Complexity Theory Retrospective II, pp. 295–328, 1997.
↑ ^7.0 ^7.1 ^7.2 ^7.3 ^7.4 ^7.5 ^7.6 ^7.7 ^7.8 S. Arora and B. Barak, Computational Complexity: A Modern Approach, Cambridge University Press, New York, NY, 2009.
↑ Y. Gurevich, "Complete and incomplete randomized NP problems", Proc. 28th Annual Symp. on Found. of Computer Science, IEEE (1987), pp. 111–117.
↑ N. Livne, "All Natural NP-Complete Problems Have Average-Case Complete Versions," Computational Complexity (2010) 19:477. https://doi.org/10.1007/s00037-010-0298-9
↑ O. Goldreich, "Notes on Levin's theory of average-case complexity," Technical Report TR97-058, Electronic Colloquium on Computational Complexity, 1997.
↑ J. Katz and Y. Lindell, Introduction to Modern Cryptography (Chapman and Hall/Crc Cryptography and Network Security Series), Chapman and Hall/CRC, 2007.
↑ R. Impagliazzo and L. Levin, "No Better Ways to Generate Hard NP Instances than Picking Uniformly at Random," in Proceedings of the 31st IEEE Sympo- sium on Foundations of Computer Science, pp. 812–821, 1990.
↑ S. Ben-David, B. Chor, O. Goldreich, and M. Luby, "On the theory of average case complexity," Journal of Computer and System Sciences, vol. 44, no. 2, pp. 193–219, 1992.
↑ J. Feigenbaum and L. Fortnow, "Random-self-reducibility of complete sets," SIAM Journal on Computing, vol. 22, pp. 994–1005, 1993.
↑ A. Bogdanov and L. Trevisan, "On worst-case to average-case reductions for NP problems," in Proceedings of the 44th IEEE Symposium on Foundations of Computer Science, pp. 308–317, 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.

[gol07-1] O. Goldreich and S. Vadhan, Special issue on worst-case versus average-case complexity, Comput. Complex. 16, 325–330, 2007.

[clrs-2] 2.0 ^2.1 Cormen, Thomas H.; Leiserson, Charles E., Rivest, Ronald L., Stein, Clifford (2009) [1990]. Introduction to Algorithms (3rd ed.). MIT Press and McGraw-Hill. ISBN 0-262-03384-4.

[bog06-3] 3.0 ^3.1 ^3.2 ^3.3 ^3.4 ^3.5 A. Bogdanov and L. Trevisan, "Average-Case Complexity," Foundations and Trends in Theoretical Computer Science, Vol. 2, No 1 (2006) 1–106.

[knu73-4] D. Knuth, The Art of Computer Programming. Vol. 3, Addison-Wesley, 1973.

[levin86-5] 5.0 ^5.1 L. Levin, "Average case complete problems," SIAM Journal on Computing, vol. 15, no. 1, pp. 285–286, 1986.

[wangsurvey-6] 6.0 ^6.1 ^6.2 J. Wang, "Average-case computational complexity theory," Complexity Theory Retrospective II, pp. 295–328, 1997.

[ab09-7] 7.0 ^7.1 ^7.2 ^7.3 ^7.4 ^7.5 ^7.6 ^7.7 ^7.8 S. Arora and B. Barak, Computational Complexity: A Modern Approach, Cambridge University Press, New York, NY, 2009.

[gur87-8] Y. Gurevich, "Complete and incomplete randomized NP problems", Proc. 28th Annual Symp. on Found. of Computer Science, IEEE (1987), pp. 111–117.

[livne06-9] N. Livne, "All Natural NP-Complete Problems Have Average-Case Complete Versions," Computational Complexity (2010) 19:477. https://doi.org/10.1007/s00037-010-0298-9

[gol97-10] O. Goldreich, "Notes on Levin's theory of average-case complexity," Technical Report TR97-058, Electronic Colloquium on Computational Complexity, 1997.

[katz07-11] J. Katz and Y. Lindell, Introduction to Modern Cryptography (Chapman and Hall/Crc Cryptography and Network Security Series), Chapman and Hall/CRC, 2007.

[imp90-12] R. Impagliazzo and L. Levin, "No Better Ways to Generate Hard NP Instances than Picking Uniformly at Random," in Proceedings of the 31st IEEE Sympo- sium on Foundations of Computer Science, pp. 812–821, 1990.

[bd92-13] S. Ben-David, B. Chor, O. Goldreich, and M. Luby, "On the theory of average case complexity," Journal of Computer and System Sciences, vol. 44, no. 2, pp. 193–219, 1992.

[ff93-14] J. Feigenbaum and L. Fortnow, "Random-self-reducibility of complete sets," SIAM Journal on Computing, vol. 22, pp. 994–1005, 1993.

[bog03-15] A. Bogdanov and L. Trevisan, "On worst-case to average-case reductions for NP problems," in Proceedings of the 44th IEEE Symposium on Foundations of Computer Science, pp. 308–317, 2003.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

@@ Line 1: / Line 1: @@
 {{redirect|औसत.पी|अन्य उपयोग|औसत पी (असंबद्धता)}}
-[[कम्प्यूटेशनल जटिलता सिद्धांत]] में, एक [[कलन विधि]] की औसत-केस जटिलता कलन विधि द्वारा उपयोग किए जाने वाले कुछ कम्प्यूटेशनल संसाधन (आमतौर पर समय) की मात्रा है, जो सभी संभावित इनपुट पर औसत होती है। इसकी तुलना अक्सर सबसे खराब स्थिति वाली जटिलता से की जाती है जो सभी संभावित इनपुटों पर कलन विधि की अधिकतम जटिलता पर विचार करती है।
+[[कम्प्यूटेशनल जटिलता सिद्धांत]] में, एक [[कलन विधि]] की औसत-केस जटिलता कलन विधि द्वारा उपयोग किए जाने वाले कुछ कम्प्यूटेशनल संसाधन (सामान्यतः समय) की मात्रा है, जो सभी संभावित इनपुट पर औसत होती है। इसकी तुलना प्रायः सबसे खराब स्थिति वाली जटिलता से की जाती है जो सभी संभावित इनपुटों पर कलन विधि की अधिकतम जटिलता पर विचार करती है।
 औसत-कारक की जटिलता का अध्ययन करने के लिए तीन प्राथमिक प्रेरणाएँ हैं।<ref name="gol07">O. Goldreich and S. Vadhan, Special issue on worst-case versus average-case complexity, Comput. Complex. 16, 325–330, 2007.</ref> सबसे पहले, हालांकि कुछ समस्याएं सबसे खराब स्थिति में कठिन हो सकती हैं, लेकिन इस व्यवहार को उत्पन्न करने वाले इनपुट व्यवहार में शायद ही कभी हो सकते हैं, इसलिए औसत-कारक की जटिलता कलन विधि के प्रदर्शन का अधिक सटीक माप हो सकती है। दूसरा, औसत-कारक जटिलता विश्लेषण समस्याओं के कठिन उदाहरण उत्पन्न करने के लिए उपकरण और तकनीक प्रदान करता है जिसका उपयोग [[क्रिप्टोग्राफी]] और [[व्युत्पन्नकरण]] जैसे क्षेत्रों में किया जा सकता है। तीसरा, औसत-कारक जटिलता समतुल्य सर्वोत्तम-कारक जटिलता (उदाहरण के लिए क्विकॉर्ट) के कलन विधि के बीच व्यवहार में सबसे कुशल कलन विधि को भेदभाव करने की अनुमति देती है।
-औसत-कारक विश्लेषण के लिए एक कलन विधि में "औसत" इनपुट की धारणा की आवश्यकता होती है, जिससे इनपुट पर संभाव्यता वितरण तैयार करने की समस्या पैदा होती है। वैकल्पिक रूप से, [[यादृच्छिक एल्गोरिदम|यादृच्छिक कलन विधि]] का उपयोग किया जा सकता है। ऐसे कलन विधि के विश्लेषण से अपेक्षित जटिलता की संबंधित धारणा सामने आती है।<ref name="clrs"/>
+औसत-कारक विश्लेषण के लिए एक कलन विधि में "औसत" इनपुट की धारणा की आवश्यकता होती है, जिससे इनपुट पर संभाव्यता वितरण तैयार करने की समस्या उत्पन्न होती है। वैकल्पिक रूप से, [[यादृच्छिक एल्गोरिदम|यादृच्छिक कलन विधि]] का उपयोग किया जा सकता है। ऐसे कलन विधि के विश्लेषण से अपेक्षित जटिलता की संबंधित धारणा सामने आती है।<ref name="clrs"/>
 ==इतिहास और पृष्ठभूमि==
@@ Line 10: / Line 10: @@
 के दशक में कम्प्यूटेशनल दक्षता की आधुनिक धारणाएँ विकसित होने के बाद से कलन विधि के औसत-केस प्रदर्शन का अध्ययन किया गया है। इस आरंभिक कार्य का अधिकांश भाग उन समस्याओं पर केंद्रित था जिनके लिए सबसे खराब स्थिति वाले बहुपद समय कलन विधि पहले से ही ज्ञात थे।<ref name="bog06">A. Bogdanov and L. Trevisan, "Average-Case Complexity," Foundations and Trends in Theoretical Computer Science, Vol. 2, No 1 (2006) 1–106.</ref>1973 में, [[डोनाल्ड नुथ]]<ref name="knu73">D. Knuth, [[The Art of Computer Programming]]. Vol. 3, Addison-Wesley, 1973.</ref> ने आर्ट ऑफ़ [[कंप्यूटर प्रोग्रामिंग की कला|कंप्यूटर प्रोग्रामिंग]] का खंड 3 प्रकाशित किया, जो सॉर्टिंग और मीडियन-फाइंडिंग जैसी सबसे खराब स्थिति वाले बहुपद समय में हल करने योग्य समस्याओं के लिए कलन विधि के औसत-केस प्रदर्शन का व्यापक सर्वेक्षण करता है।
-{{math|'''NP'''}}-पूर्ण समस्याओं के लिए एक कुशल कलन विधि को आम तौर पर ऐसे कलन विधि के रूप में जाना जाता है जो सभी इनपुट के लिए बहुपद समय में चलता है; यह सबसे खराब स्थिति में कुशल जटिलता की आवश्यकता के बराबर है। हालाँकि, एक एल्गोरिथ्म जो "छोटी" संख्या में इनपुट पर अक्षम है, वह अभी भी व्यवहार में आने वाले "अधिकांश" इनपुट के लिए कुशल हो सकता है। इस प्रकार, इन कलन विधि के गुणों का अध्ययन करना वांछनीय है जहां औसत-कारक की जटिलता सबसे खराब-कारक की जटिलता से भिन्न हो सकती है और दोनों को संबंधित करने के तरीकों को ढूंढना है।
+{{math|'''NP'''}}-पूर्ण समस्याओं के लिए एक कुशल कलन विधि को सामान्यतः ऐसे कलन विधि के रूप में जाना जाता है जो सभी इनपुट के लिए बहुपद समय में चलता है; यह सबसे खराब स्थिति में कुशल जटिलता की आवश्यकता के बराबर है। हालाँकि, एक एल्गोरिथ्म जो "छोटी" संख्या में इनपुट पर अक्षम है, वह अभी भी व्यवहार में आने वाले "अधिकांश" इनपुट के लिए कुशल हो सकता है। इस प्रकार, इन कलन विधि के गुणों का अध्ययन करना वांछनीय है जहां औसत-कारक की जटिलता सबसे खराब-कारक की जटिलता से भिन्न हो सकती है और दोनों को संबंधित करने के तरीकों को ढूंढना है।
 औसत-कारक की जटिलता की मौलिक धारणाएं 1986 में [[लियोनिद लेविन]] द्वारा विकसित की गईं जब उन्होंने एक पेज का पेपर प्रकाशित किया।<ref name="levin86">L. Levin, "Average case complete problems," SIAM Journal on Computing, vol. 15, no. 1, pp. 285–286, 1986.</ref> {{math|'''NP'''}} के औसत-केस एनालॉग, {{math|'''distNP'''}} के लिए एक संपूर्ण समस्या का उदाहरण देते हुए औसत-केस जटिलता और पूर्णता को परिभाषित करना है।
@@ Line 18: / Line 18: @@
 ===कुशल औसत-कारक की जटिलता===
-पहला कार्य यह स्पष्ट रूप से परिभाषित करना है कि एक कलन विधि का क्या मतलब है जो "औसतन" कुशल है। प्रारंभिक प्रयास एक कुशल औसत-केस कलन विधि को परिभाषित कर सकता है जो सभी संभावित इनपुट पर अपेक्षित बहुपद समय में चलता है। ऐसी परिभाषा में कई कमियाँ हैं; विशेष रूप से, यह कम्प्यूटेशनल मॉडल में परिवर्तन के लिए मजबूत नहीं है। उदाहरण के लिए, मान लीजिए कि कलन विधि {{mvar|A}} इनपुट {{mvar|x}} पर समय {{math|''t''<sub>''A''</sub>(''x'')}} में चलता है और कलन विधि {{mvar|B}} इनपुट {{mvar|x}} पर समय {{math|''t''<sub>''A''</sub>(''x'')<sup>2</sup>}} में चलता है; अर्थात्, {{mvar|B}}, {{mvar|A}} की तुलना में चतुष्कोणीय रूप से धीमा है। सहज रूप से, औसत-कारक की दक्षता की किसी भी परिभाषा में इस विचार को शामिल किया जाना चाहिए कि {{mvar|A}} औसत पर कुशल है यदि और केवल यदि {{mvar|B}} औसत पर कुशल है। हालाँकि, मान लीजिए कि इनपुट लंबाई {{mvar|n}} के साथ स्ट्रिंग के समान वितरण से यादृच्छिक रूप से निकाले जाते हैं, और {{mvar|A}} स्ट्रिंग {{math|1<sup>''n''</sup>}} को छोड़कर सभी इनपुट पर समय {{math|''n''<sup>2</sup>}} में चलता है जिसके लिए {{mvar|A}} को {{math|2<sup>''n''</sup>}} समय लगता है। तब यह आसानी से जांचा जा सकता है कि {{mvar|A}} का अपेक्षित रनिंग समय बहुपद है लेकिन {{mvar|B}} का पेक्षित चलने का समय घातीय है।<ref name="bog06" />
+पहला कार्य यह स्पष्ट रूप से परिभाषित करना है कि कलन विधि का क्या मतलब है जो "औसतन" कुशल है। प्रारंभिक प्रयास कुशल औसत-केस कलन विधि को परिभाषित कर सकता है जो सभी संभावित इनपुट पर अपेक्षित बहुपद समय में चलता है। ऐसी परिभाषा में कई कमियाँ हैं; विशेष रूप से, यह कम्प्यूटेशनल मॉडल में परिवर्तन के लिए मजबूत नहीं है। उदाहरण के लिए, मान लीजिए कि कलन विधि {{mvar|A}} इनपुट {{mvar|x}} पर समय {{math|''t''<sub>''A''</sub>(''x'')}} में चलता है और कलन विधि {{mvar|B}} इनपुट {{mvar|x}} पर समय {{math|''t''<sub>''A''</sub>(''x'')<sup>2</sup>}} में चलता है; अर्थात्, {{mvar|B}}, {{mvar|A}} की तुलना में चतुष्कोणीय रूप से धीमा है। सहज रूप से, औसत-कारक की दक्षता की किसी भी परिभाषा में इस विचार को सम्मिलित किया जाना चाहिए कि {{mvar|A}} औसत पर कुशल है यदि और केवल यदि {{mvar|B}} औसत पर कुशल है। हालाँकि, मान लीजिए कि इनपुट लंबाई {{mvar|n}} के साथ स्ट्रिंग के समान वितरण से यादृच्छिक रूप से निकाले जाते हैं, और {{mvar|A}} स्ट्रिंग {{math|1<sup>''n''</sup>}} को छोड़कर सभी इनपुट पर समय {{math|''n''<sup>2</sup>}} में चलता है जिसके लिए {{mvar|A}} को {{math|2<sup>''n''</sup>}} समय लगता है। तब यह आसानी से जांचा जा सकता है कि {{mvar|A}} का अपेक्षित रनिंग समय बहुपद है लेकिन {{mvar|B}} का पेक्षित चलने का समय घातीय है।<ref name="bog06" />
-औसत-केस दक्षता की अधिक मजबूत परिभाषा बनाने के लिए, एक कलन विधि की अनुमति देना समझ में आता है {{mvar|A}} कुछ इनपुट पर बहुपद समय से अधिक समय तक चलने के लिए लेकिन जिस पर इनपुट का अंश {{mvar|A}} बड़ी और बड़ी आवश्यकता होती है, चलने का समय छोटा और छोटा होता जाता है। इस अंतर्ज्ञान को औसत बहुपद चलने वाले समय के लिए निम्नलिखित सूत्र में कैद किया गया है, जो चलने वाले समय और इनपुट के अंश के बीच बहुपद व्यापार-बंद को संतुलित करता है:
+औसत-केस दक्षता की अधिक मजबूत परिभाषा बनाने के लिए, कलन विधि की अनुमति देना समझ में आता है {{mvar|A}} कुछ इनपुट पर बहुपद समय से अधिक समय तक चलने के लिए लेकिन जिस पर इनपुट का अंश {{mvar|A}} बड़ी और बड़ी आवश्यकता होती है, चलने का समय छोटा और छोटा होता जाता है। इस अंतर्ज्ञान को औसत बहुपद चलने वाले समय के लिए निम्नलिखित सूत्र में कैद किया गया है, जो चलने वाले समय और इनपुट के अंश के बीच बहुपद व्यापार-बंद को संतुलित करता है:
 :<math>
 \Pr_{x \in_R D_n} \left[t_A(x) \geq t \right] \leq \frac{p(n)}{t^\epsilon}
 </math>
-हरएक के लिए {{math|''n'', ''t'' &gt; 0}} और बहुपद {{mvar|p}}, कहाँ {{math|''t''<sub>''A''</sub>(''x'')}} एल्गोरिथम के चलने के समय को दर्शाता है {{mvar|A}} इनपुट पर {{mvar|x}}, और {{mvar|ε}} एक सकारात्मक स्थिरांक मान है.<ref name="wangsurvey">J. Wang, "Average-case computational complexity theory,"  Complexity Theory Retrospective II,  pp. 295–328, 1997.</ref> वैकल्पिक रूप से, इसे इस प्रकार लिखा जा सकता है
+हरएक के लिए {{math|''n'', ''t'' &gt; 0}} और बहुपद {{mvar|p}}, जहाँ {{math|''t''<sub>''A''</sub>(''x'')}} एल्गोरिथम के चलने के समय को दर्शाता है {{mvar|A}} इनपुट पर {{mvar|x}}, और {{mvar|ε}} धनात्मक स्थिरांक मान है.<ref name="wangsurvey">J. Wang, "Average-case computational complexity theory,"  Complexity Theory Retrospective II,  pp. 295–328, 1997.</ref> वैकल्पिक रूप से, इसे इस प्रकार लिखा जा सकता है
 :<math>
 E_{x \in_R D_n} \left[ \frac{t_{A}(x)^{\epsilon}}{n} \right] \leq C
 </math>
-कुछ स्थिरांक {{mvar|C}} और {{mvar|ε}} के लिए, जहां {{math|''n'' {{=}} {{abs|''x''}}}}<ref name="ab09">S. Arora and B. Barak, Computational Complexity: A Modern Approach, Cambridge University Press, New York, NY, 2009.</ref> दूसरे शब्दों में, एक एल्गोरिदम {{mvar|A}} में औसत-कारक की जटिलता अच्छी होती है, यदि {{math|''t''<sub>''A''</sub>(''n'')}} चरणों के लिए चलने के बाद, ''A'' कुछ {{math|''ε'', ''c'' &gt; 0}} के लिए लंबाई {{mvar|n}} के इनपुट के {{math|{{sfrac|''n''<sup>''c''</sup>|(''t''<sub>''A''</sub>(''n''))<sup>''ε''</sup>}}}} अंश को छोड़कर सभी को हल कर सकता है।<ref name="bog06"/>
+कुछ स्थिरांक {{mvar|C}} और {{mvar|ε}} के लिए, जहां {{math|''n'' {{=}} {{abs|''x''}}}}<ref name="ab09">S. Arora and B. Barak, Computational Complexity: A Modern Approach, Cambridge University Press, New York, NY, 2009.</ref> दूसरे शब्दों में, कलन विधि {{mvar|A}} में औसत-कारक की जटिलता अच्छी होती है, यदि {{math|''t''<sub>''A''</sub>(''n'')}} चरणों के लिए चलने के बाद, ''A'' कुछ {{math|''ε'', ''c'' &gt; 0}} के लिए लंबाई {{mvar|n}} के इनपुट के {{math|{{sfrac|''n''<sup>''c''</sup>|(''t''<sub>''A''</sub>(''n''))<sup>''ε''</sup>}}}} अंश को छोड़कर सभी को हल कर सकता है।<ref name="bog06"/>
 ===वितरण संबंधी समस्या===
-अगला कदम एक विशेष समस्या के लिए "औसत" इनपुट को परिभाषित करना है। यह प्रत्येक समस्या के इनपुट को एक विशेष संभावना वितरण के साथ जोड़कर हासिल किया जाता है। अर्थात्, एक औसत-कारक की समस्या में एक भाषा शामिल होती है {{mvar|L}} और एक संबद्ध संभाव्यता {{mvar|D}} वितरण {{math|(''L'', ''D'')}} जो जोड़ी बनाता है .<ref name="ab09"/> वितरण के दो सबसे सामान्य वर्ग जिनकी अनुमति है वे हैं:
+अगला कदम एक विशेष समस्या के लिए "औसत" इनपुट को परिभाषित करना है। यह प्रत्येक समस्या के इनपुट को एक विशेष संभावना वितरण के साथ जोड़कर हासिल किया जाता है। अर्थात्, औसत-कारक की समस्या में एक भाषा सम्मिलित होती है {{mvar|L}} और संबद्ध संभाव्यता {{mvar|D}} वितरण {{math|(''L'', ''D'')}} जो जोड़ी बनाता है .<ref name="ab09"/> वितरण के दो सबसे सामान्य वर्ग जिनकी अनुमति है वे हैं:
-#बहुपद-समय गणना योग्य वितरण ({{math|'''P'''}}-कंप्यूटेबल): ये ऐसे वितरण हैं जिनके लिए किसी दिए गए इनपुट {{mvar|x}} के संचयी घनत्व की गणना करना संभव है। अधिक औपचारिक रूप से, संभाव्यता वितरण {{mvar|μ}} और एक स्ट्रिंग {{math|''x'' &isin; {{mset|0, 1}}<sup>''n''</sup>}} को देखते हुए, बहुपद समय में मान <math>\mu(x) = \sum\limits_{y \in \{0, 1\}^n : y \leq x} \Pr[y]</math> की गणना करना संभव है। इसका तात्पर्य यह है कि {{math|Pr[''x'']}} की गणना बहुपद समय में भी की जा सकती है।
+#बहुपद-समय गणना योग्य वितरण ({{math|'''P'''}}-कंप्यूटेबल): ये ऐसे वितरण हैं जिनके लिए किसी दिए गए इनपुट {{mvar|x}} के संचयी घनत्व की गणना करना संभव है। अधिक औपचारिक रूप से, संभाव्यता वितरण {{mvar|μ}} और स्ट्रिंग {{math|''x'' &isin; {{mset|0, 1}}<sup>''n''</sup>}} को देखते हुए, बहुपद समय में मान <math>\mu(x) = \sum\limits_{y \in \{0, 1\}^n : y \leq x} \Pr[y]</math> की गणना करना संभव है। इसका तात्पर्य यह है कि {{math|Pr[''x'']}} की गणना बहुपद समय में भी की जा सकती है।
 #बहुपद-समय नमूना वितरण ({{math|'''P'''}}-नमूना): ये ऐसे वितरण हैं जिनसे बहुपद समय में यादृच्छिक नमूने निकालना संभव है।
 ये दोनों सूत्रीकरण, समान होते हुए भी, समतुल्य नहीं हैं। यदि कोई वितरण {{math|'''P'''}}-गणना योग्य है तो यह भी {{math|'''P'''}}-नमूना योग्य है, लेकिन यदि {{math|'''P'''}}≠{{math|'''P'''<sup>'''#P'''</sup>}} है तो इसका विपरीत सत्य नहीं है।<ref name="ab09"/>
 ===एवीजीपी और डिस्टएनपी===
-एक वितरण संबंधी समस्या {{math|(''L'', ''D'')}} जटिलता वर्ग में है {{math|'''AvgP'''}} यदि इसके लिए एक कुशल औसत-केस {{mvar|L}} कलन विधि है, जैसा कि ऊपर परिभाषित किया गया है। वर्ग {{math|'''AvgP'''}} को कभी-कभी साहित्य में {{math|'''distP'''}} कहा जाता है।<ref name="ab09"/>
+वितरण संबंधी समस्या {{math|(''L'', ''D'')}} जटिलता वर्ग में है {{math|'''AvgP'''}} यदि इसके लिए एक कुशल औसत-केस {{mvar|L}} कलन विधि है, जैसा कि ऊपर परिभाषित किया गया है। वर्ग {{math|'''AvgP'''}} को कभी-कभी साहित्य में {{math|'''distP'''}} कहा जाता है।<ref name="ab09"/>
-एक वितरण संबंधी समस्या {{math|(''L'', ''D'')}} जटिलता वर्ग {{math|'''distNP'''}} में है यदि {{mvar|L}} {{math|'''NP'''}} में है और {{mvar|D}} {{math|'''P'''}}-कंप्यूटेबल है। जब {{mvar|L}} {{math|'''NP'''}} में है और {{mvar|D}} {{math|'''P'''}}-नमूना योग्य है, {{math|(''L'', ''D'')}} {{math|'''sampNP'''}} से संबंधित है।<ref name="ab09"/>
+वितरण संबंधी समस्या {{math|(''L'', ''D'')}} जटिलता वर्ग {{math|'''distNP'''}} में है यदि {{mvar|L}} {{math|'''NP'''}} में है और {{mvar|D}} {{math|'''P'''}}-कंप्यूटेबल है। जब {{mvar|L}} {{math|'''NP'''}} में है और {{mvar|D}} {{math|'''P'''}}-नमूना योग्य है, {{math|(''L'', ''D'')}} {{math|'''sampNP'''}} से संबंधित है।<ref name="ab09"/>
 साथ में, {{math|'''AvgP'''}} और {{math|'''distNP'''}} क्रमशः {{math|'''P'''}} और {{math|'''NP'''}} के औसत-केस एनालॉग्स को परिभाषित करते हैं।<ref name="ab09"/>
@@ Line 49: / Line 49: @@
 #(सहीता) {{math|''x'' ∈ ''L''}} यदि और केवल यदि {{math|''f''(''x'') ∈ ''L&prime;''}}
 #(प्रभुत्व) बहुपद होते हैं {{mvar|p}} और {{mvar|m}} ऐसा कि, प्रत्येक {{mvar|n}} और {{mvar|y}} के लिए, <math>\sum\limits_{x: f(x) = y} D_n(x) \leq p(n)D'_{m(n)}(y)</math>
-प्रभुत्व की स्थिति इस धारणा को लागू करती है कि यदि समस्या है {{math|(''L'', ''D'')}} तो फिर औसत रूप से कठिन है {{math|(''L&prime;'', ''D&prime;'')}} औसत रूप से भी कठिन है। सहज रूप से, कमी को किसी उदाहरण को हल करने का एक तरीका प्रदान करना चाहिए {{mvar|x}}समस्या का {{mvar|L}} कंप्यूटिंग द्वारा {{math|''f''(''x'')}} और आउटपुट को कलन विधि को फीड करना जो हल करता है {{mvar|L'}}. प्रभुत्व की स्थिति के बिना, यह संभव नहीं हो सकता है क्योंकि कलन विधि जो हल करता है {{mvar|L}} बहुपद समय में औसतन कम संख्या में इनपुट पर सुपर-बहुपद समय लग सकता है {{mvar|f}} इन इनपुटों को बहुत बड़े सेट में मैप कर सकता है {{mvar|D'}} तो वह कलन विधि {{mvar|A'}} अब औसतन बहुपद समय में नहीं चलता। प्रभुत्व की स्थिति केवल ऐसे श्रृंखला को बहुपद रूप से घटित होने की अनुमति देती है जैसा कि अक्सर {{mvar|D'}} होता है।<ref name="wangsurvey"/>
+प्रभुत्व की स्थिति इस धारणा को लागू करती है कि यदि समस्या है {{math|(''L'', ''D'')}} तो फिर औसत रूप से कठिन है {{math|(''L&prime;'', ''D&prime;'')}} औसत रूप से भी कठिन है। सहज रूप से, कमी को किसी उदाहरण को हल करने का एक तरीका प्रदान करना चाहिए {{mvar|x}}समस्या का {{mvar|L}} कंप्यूटिंग द्वारा {{math|''f''(''x'')}} और आउटपुट को कलन विधि को फीड करना जो हल करता है {{mvar|L'}}. प्रभुत्व की स्थिति के बिना, यह संभव नहीं हो सकता है क्योंकि कलन विधि जो हल करता है {{mvar|L}} बहुपद समय में औसतन कम संख्या में इनपुट पर सुपर-बहुपद समय लग सकता है {{mvar|f}} इन इनपुटों को बहुत बड़े सेट में मैप कर सकता है {{mvar|D'}} तो वह कलन विधि {{mvar|A'}} अब औसतन बहुपद समय में नहीं चलता। प्रभुत्व की स्थिति केवल ऐसे श्रृंखला को बहुपद रूप से घटित होने की अनुमति देती है जैसा कि प्रायः {{mvar|D'}} होता है।<ref name="wangsurvey"/>
 ===डिस्टएनपी-पूर्ण समस्याएं===
-औसत-केस एनालॉग {{math|'''NP'''}}-सम्पूर्णता है {{math|'''distNP'''}}-सम्पूर्णता. एक वितरण संबंधी समस्या {{math|(''L&prime;'', ''D&prime;'')}} है {{math|'''distNP'''}}-पूर्ण करें यदि {{math|(''L&prime;'', ''D&prime;'')}} में है {{math|'''distNP'''}} और प्रत्येक के लिए {{math|(''L'', ''D'')}} में {{math|'''distNP'''}}, {{math|(''L'', ''D'')}} औसत-कारक {{math|(''L&prime;'', ''D&prime;'')}} को कम करने योग्य है।<ref name="ab09" />
+औसत-केस एनालॉग {{math|'''NP'''}}-सम्पूर्णता है {{math|'''distNP'''}}-सम्पूर्णता वितरण संबंधी समस्या {{math|(''L&prime;'', ''D&prime;'')}} है {{math|'''distNP'''}}-पूर्ण करें यदि {{math|(''L&prime;'', ''D&prime;'')}} में है {{math|'''distNP'''}} और प्रत्येक के लिए {{math|(''L'', ''D'')}} में {{math|'''distNP'''}}, {{math|(''L'', ''D'')}} औसत-कारक {{math|(''L&prime;'', ''D&prime;'')}} को कम करने योग्य है।<ref name="ab09" />
 ''A'' का एक उदाहरण {{math|'''distNP'''}}-पूर्ण समस्या बाउंडेड हॉल्टिंग समस्या है, {{mvar|BH}}, इस प्रकार परिभाषित:
@@ Line 57: / Line 57: @@
 <math>BH = \{(M, x, 1^t) : M \text{ is a non-deterministic Turing machine that accepts } x \text{ in} \leq t \text{ steps}\}</math><ref name="ab09"/>
-अपने मूल पेपर में, लेविन ने वितरणात्मक टाइलिंग समस्या का एक उदाहरण दिखाया जो औसत-कारक है {{math|'''NP'''}}-पूरा।<ref name="levin86"/> ज्ञात का एक सर्वेक्षण {{math|'''distNP'''}}-सम्पूर्ण समस्याएँ ऑनलाइन उपलब्ध है।<ref name="wangsurvey"/>
+अपने मूल पेपर में, लेविन ने वितरणात्मक टाइलिंग समस्या का उदाहरण दिखाया जो औसत-कारक है {{math|'''NP'''}}-पूरा।<ref name="levin86"/> ज्ञात का सर्वेक्षण {{math|'''distNP'''}}-सम्पूर्ण समस्याएँ ऑनलाइन उपलब्ध है।<ref name="wangsurvey"/>
-सक्रिय अनुसंधान के एक क्षेत्र में नया खोजना शामिल है {{math|'''distNP'''}}-पूर्ण समस्याएँ। हालाँकि, गुरेविच के परिणाम के कारण ऐसी समस्याओं का पता लगाना जटिल हो सकता है जो दर्शाता है कि एक फ्लैट वितरण के साथ कोई भी वितरण समस्या नहीं हो सकती है {{math|'''distNP'''}}-जब तक EXP|पूर्ण न हो जाए{{math|'''EXP'''}} = NEXP|{{math|'''NEXP'''}}.<ref name="gur87">Y. Gurevich, "Complete and incomplete randomized NP problems", Proc. 28th Annual Symp. on Found. of Computer Science, IEEE (1987), pp. 111–117.</ref> (एक फ्लैट वितरण {{mvar|μ}} वह है जिसके लिए एक मौजूद है {{math|''ε'' &gt; 0}} ऐसा कि किसी के लिए भी {{mvar|x}}, {{math|''μ''(''x'') ≤ 2<sup>−{{abs|''x''}}<sup>''ε''</sup></sup>}}.) लिव्ने के एक परिणाम से पता चलता है कि सब कुछ प्राकृतिक है {{math|'''NP'''}}-पूर्ण समस्याएँ हैं {{math|'''DistNP'''}}-पूर्ण संस्करण।<ref name="livne06">N. Livne, "All Natural NP-Complete Problems Have Average-Case Complete Versions," Computational Complexity (2010) 19:477. https://doi.org/10.1007/s00037-010-0298-9</ref> हालाँकि, एक प्राकृतिक वितरणात्मक समस्या को खोजने का लक्ष्य यही है {{math|'''DistNP'''}}-अभी तक पूरा नहीं हो पाया है.<ref name="gol97">O. Goldreich, "Notes on Levin's theory of average-case complexity," Technical Report TR97-058, Electronic Colloquium on Computational Complexity, 1997.</ref>
+सक्रिय अनुसंधान के एक क्षेत्र में नया खोजना सम्मिलित है {{math|'''distNP'''}}-पूर्ण समस्याएँ। हालाँकि, गुरेविच के परिणाम के कारण ऐसी समस्याओं का पता लगाना जटिल हो सकता है जो दर्शाता है कि समतल वितरण के साथ कोई भी वितरण समस्या नहीं हो सकती है {{math|'''distNP'''}}-जब तक EXP|पूर्ण न हो जाए{{math|'''EXP'''}} = NEXP|{{math|'''NEXP'''}}.<ref name="gur87">Y. Gurevich, "Complete and incomplete randomized NP problems", Proc. 28th Annual Symp. on Found. of Computer Science, IEEE (1987), pp. 111–117.</ref> (समतल वितरण {{mvar|μ}} वह है जिसके लिए उपस्थित है {{math|''ε'' &gt; 0}} ऐसा कि किसी के लिए भी {{mvar|x}}, {{math|''μ''(''x'') ≤ 2<sup>−{{abs|''x''}}<sup>''ε''</sup></sup>}}.) लिव्ने के परिणाम से पता चलता है कि सब कुछ प्राकृतिक है {{math|'''NP'''}}-पूर्ण समस्याएँ हैं {{math|'''DistNP'''}}-पूर्ण संस्करण।<ref name="livne06">N. Livne, "All Natural NP-Complete Problems Have Average-Case Complete Versions," Computational Complexity (2010) 19:477. https://doi.org/10.1007/s00037-010-0298-9</ref> हालाँकि, एक प्राकृतिक वितरणात्मक समस्या को खोजने का लक्ष्य यही है {{math|'''DistNP'''}}-अभी तक पूरा नहीं हो पाया है.<ref name="gol97">O. Goldreich, "Notes on Levin's theory of average-case complexity," Technical Report TR97-058, Electronic Colloquium on Computational Complexity, 1997.</ref>
 अनुप्रयोग
 ===सॉर्टिंग कलन विधि===
-जैसा कि ऊपर उल्लेख किया गया है, औसत-कारक की जटिलता से संबंधित बहुत से प्रारंभिक कार्य उन समस्याओं पर केंद्रित थे जिनके लिए बहुपद-समय कलन विधि पहले से मौजूद थे, जैसे कि सॉर्टिंग। उदाहरण के लिए, कई सॉर्टिंग कलन विधि जो यादृच्छिकता का उपयोग करते हैं, जैसे कि [[जल्दी से सुलझाएं]], का चलने का समय सबसे खराब होता है {{math|O(''n''<sup>2</sup>)}}, लेकिन औसत केस चलने का समय {{math|O(''n'' log(''n''))}}, कहाँ {{mvar|n}} सॉर्ट किए जाने वाले इनपुट की लंबाई है।<ref name="clrs">Cormen, Thomas H.; Leiserson, Charles E., Rivest, Ronald L., Stein, Clifford (2009) [1990]. Introduction to Algorithms (3rd ed.). MIT Press and McGraw-Hill. {{ISBN|0-262-03384-4}}.</ref>
+जैसा कि ऊपर उल्लेख किया गया है, औसत-कारक की जटिलता से संबंधित बहुत से प्रारंभिक कार्य उन समस्याओं पर केंद्रित थे जिनके लिए बहुपद-समय कलन विधि पहले से उपस्थित थे, जैसे कि सॉर्टिंग। उदाहरण के लिए, कई सॉर्टिंग कलन विधि जो यादृच्छिकता का उपयोग करते हैं, जैसे कि [[जल्दी से सुलझाएं]], का चलने का समय सबसे खराब होता है {{math|O(''n''<sup>2</sup>)}}, लेकिन औसत केस चलने का समय {{math|O(''n'' log(''n''))}}, जहाँ {{mvar|n}} सॉर्ट किए जाने वाले इनपुट की लंबाई है।<ref name="clrs">Cormen, Thomas H.; Leiserson, Charles E., Rivest, Ronald L., Stein, Clifford (2009) [1990]. Introduction to Algorithms (3rd ed.). MIT Press and McGraw-Hill. {{ISBN|0-262-03384-4}}.</ref>
 ===क्रिप्टोग्राफी===
-अधिकांश समस्याओं के लिए, किसी समस्या के लिए कुशल एल्गोरिदम खोजने के लिए औसत-कारक जटिलता विश्लेषण किया जाता है जिसे सबसे खराब स्थिति में कठिन माना जाता है। क्रिप्टोग्राफ़िक अनुप्रयोगों में, हालांकि, विपरीत सच है: सबसे खराब स्थिति की जटिलता अप्रासंगिक है; इसके बजाय हम यह गारंटी चाहते हैं कि क्रिप्टोग्राफ़िक योजना को "तोड़ने" वाले प्रत्येक एल्गोरिदम की औसत-केस जटिलता अक्षम है।<ref name="katz07">J. Katz and Y. Lindell, Introduction to Modern Cryptography (Chapman and Hall/Crc Cryptography and Network Security Series), Chapman and Hall/CRC, 2007.</ref> इस प्रकार, सभी सुरक्षित क्रिप्टोग्राफ़िक योजनाएँ एकपक्षीय फलन के अस्तित्व पर निर्भर करती हैं।<ref name="bog06"/> हालाँकि एकपक्षीय फलन का अस्तित्व अभी भी एक रिक्त समस्या है, कई उम्मीदवार एकपक्षीय फलन [[पूर्णांक गुणनखंडन]] या असतत लॉग की गणना जैसी कठिन समस्याओं पर आधारित हैं। ध्यान दें कि उम्मीदवार के कार्य के लिए ऐसा होना वांछनीय नहीं है {{math|'''NP'''}}-पूर्ण क्योंकि यह केवल इस बात की गारंटी देगा कि सबसे खराब स्थिति में समस्या को हल करने के लिए कोई कुशल कलन विधि नहीं है; हम वास्तव में यह गारंटी चाहते हैं कि कोई भी कुशल कलन विधि यादृच्छिक इनपुट (यानी औसत कारक) पर समस्या का समाधान नहीं कर सकता है। वास्तव में, पूर्णांक गुणनखंडन {{math|'''NP''' ∩ }}औरcoNP|{{math|'''coNP'''}} असतत लॉग समस्याएँ दोनों ही हैं, और इसलिए {{math|'''NP'''}}-पूर्ण नहीं माना जाता है।<ref name="ab09"/> तथ्य यह है कि संपूर्ण क्रिप्टोग्राफी औसत-कारक में कठिन समस्याओं के अस्तित्व पर आधारित है {{math|'''NP'''}} औसत-कारक की जटिलता का अध्ययन करने के लिए प्राथमिक प्रेरणाओं में से एक है।
+अधिकांश समस्याओं के लिए, किसी समस्या के लिए कुशल कलन विधि खोजने के लिए औसत-कारक जटिलता विश्लेषण किया जाता है जिसे सबसे खराब स्थिति में कठिन माना जाता है। क्रिप्टोग्राफ़िक अनुप्रयोगों में, हालांकि, विपरीत सच है: सबसे खराब स्थिति की जटिलता अप्रासंगिक है; इसके बजाय हम यह गारंटी चाहते हैं कि क्रिप्टोग्राफ़िक योजना को "तोड़ने" वाले प्रत्येक कलन विधि की औसत-केस जटिलता अक्षम है।<ref name="katz07">J. Katz and Y. Lindell, Introduction to Modern Cryptography (Chapman and Hall/Crc Cryptography and Network Security Series), Chapman and Hall/CRC, 2007.</ref> इस प्रकार, सभी सुरक्षित क्रिप्टोग्राफ़िक योजनाएँ एकपक्षीय फलन के अस्तित्व पर निर्भर करती हैं।<ref name="bog06"/> हालाँकि एकपक्षीय फलन का अस्तित्व अभी भी एक रिक्त समस्या है, कई उम्मीदवार एकपक्षीय फलन [[पूर्णांक गुणनखंडन]] या असतत लॉग की गणना जैसी कठिन समस्याओं पर आधारित हैं। ध्यान दें कि उम्मीदवार के कार्य के लिए ऐसा होना वांछनीय नहीं है {{math|'''NP'''}}-पूर्ण क्योंकि यह केवल इस बात की गारंटी देगा कि सबसे खराब स्थिति में समस्या को हल करने के लिए कोई कुशल कलन विधि नहीं है; हम वास्तव में यह गारंटी चाहते हैं कि कोई भी कुशल कलन विधि यादृच्छिक इनपुट (यानी औसत कारक) पर समस्या का समाधान नहीं कर सकता है। वास्तव में, पूर्णांक गुणनखंडन {{math|'''NP''' ∩ }}औरcoNP|{{math|'''coNP'''}} असतत लॉग समस्याएँ दोनों ही हैं, और इसलिए {{math|'''NP'''}}-पूर्ण नहीं माना जाता है।<ref name="ab09"/> तथ्य यह है कि संपूर्ण क्रिप्टोग्राफी औसत-कारक में कठिन समस्याओं के अस्तित्व पर आधारित है {{math|'''NP'''}} औसत-कारक की जटिलता का अध्ययन करने के लिए प्राथमिक प्रेरणाओं में से एक है।
 ==अन्य परिणाम==
 में, इम्पाग्लिआज़ो और लेविन ने दिखाया कि यदि किसी के लिए एक कुशल औसत-केस कलन विधि है {{math|'''distNP'''}}-समान वितरण के तहत पूर्ण समस्या, फिर प्रत्येक समस्या के लिए एक औसत-केस कलन विधि है {{math|'''NP'''}} किसी भी बहुपद-समय नमूना योग्य वितरण के तहत।<ref name="imp90">R. Impagliazzo and L. Levin, "No Better Ways to Generate Hard NP Instances than Picking Uniformly at Random," in Proceedings of the 31st IEEE Sympo- sium on Foundations of Computer Science, pp. 812–821, 1990.</ref> इस सिद्धांत को प्राकृतिक वितरण संबंधी समस्याओं पर लागू करना एक उत्कृष्ट रिक्त प्रश्न बना हुआ है।<ref name="bog06"/>
-में, बेन-डेविड एट अल। दिखाया कि यदि सभी भाषाओं में {{math|'''distNP'''}} उनके पास औसत पर अच्छे निर्णय कलन विधि हैं, उनके पास औसत पर अच्छे खोज कलन विधि भी हैं। इसके अलावा, वे दिखाते हैं कि यह निष्कर्ष एक कमजोर धारणा के अंतर्गत आता है: यदि प्रत्येक भाषा में {{math|'''NP'''}}समान वितरण के संबंध में निर्णय कलन विधि के लिए औसत रूप से आसान है, फिर समान वितरण के संबंध में खोज कलन विधि के लिए भी यह औसत रूप से आसान है।<ref name="bd92">S. Ben-David, [[Benny Chor|B. Chor]], O. Goldreich, and M. Luby, "On the theory of average case complexity," Journal of Computer and System Sciences, vol. 44, no. 2, pp. 193–219, 1992.</ref> इस प्रकार, क्रिप्टोग्राफ़िक एकपक्षीय फलन केवल तभी मौजूद हो सकते हैं जब {{math|'''distNP'''}} वहाँ हों समान वितरण पर समस्याएं जो निर्णय कलन विधि के लिए औसतन कठिन हैं।
+में, बेन-डेविड एट अल। दिखाया कि यदि सभी भाषाओं में {{math|'''distNP'''}} उनके पास औसत पर अच्छे निर्णय कलन विधि हैं, उनके पास औसत पर अच्छे खोज कलन विधि भी हैं। इसके अलावा, वे दिखाते हैं कि यह निष्कर्ष एक कमजोर धारणा के अंतर्गत आता है: यदि प्रत्येक भाषा में {{math|'''NP'''}}समान वितरण के संबंध में निर्णय कलन विधि के लिए औसत रूप से आसान है, फिर समान वितरण के संबंध में खोज कलन विधि के लिए भी यह औसत रूप से आसान है।<ref name="bd92">S. Ben-David, [[Benny Chor|B. Chor]], O. Goldreich, and M. Luby, "On the theory of average case complexity," Journal of Computer and System Sciences, vol. 44, no. 2, pp. 193–219, 1992.</ref> इस प्रकार, क्रिप्टोग्राफ़िक एकपक्षीय फलन केवल तभी उपस्थित हो सकते हैं जब {{math|'''distNP'''}} वहाँ हों समान वितरण पर समस्याएं जो निर्णय कलन विधि के लिए औसतन कठिन हैं।
 में, फेगेनबाम और फ़ोर्टनो ने दिखाया कि गैर-अनुकूली यादृच्छिक अपचयन के तहत, यह साबित करना संभव नहीं है कि एक अच्छे-ऑन-औसत कलन विधि का अस्तित्व {{math|'''distNP'''}}-समान वितरण के तहत पूर्ण समस्या का तात्पर्य सभी समस्याओं के लिए सबसे खराब स्थिति वाले कुशल कलन विधि के अस्तित्व से है {{math|'''NP'''}}.<ref name="ff93">J. Feigenbaum and L. Fortnow, "Random-self-reducibility of complete sets," SIAM Journal on Computing, vol. 22, pp. 994–1005, 1993.</ref> 2003 में, बोगदानोव और ट्रेविसन ने इस परिणाम को मनमाने ढंग से गैर-अनुकूली अपचयन के रूप में सामान्यीकृत किया।<ref name="bog03">A. Bogdanov and L. Trevisan, "On worst-case to average-case reductions for NP problems," in Proceedings of the 44th IEEE Symposium on Foundations of Computer Science, pp. 308–317, 2003.</ref> इन परिणामों से पता चलता है कि यह संभावना नहीं है कि अपचयन के माध्यम से औसत-कारक की जटिलता और सबसे खराब-कारक की जटिलता के बीच कोई संबंध बनाया जा सकता है।<ref name="bog06"/>
@@ Line 79: / Line 79: @@
 *[[परिशोधन विश्लेषण]]
 *सबसे अच्छा, सबसे खराब और औसत कारक
-*एल्गोरिदम का संभाव्य विश्लेषण
+*कलन विधि का संभाव्य विश्लेषण
 ==संदर्भ==

Anonymous

Search

एवरेज-केस कम्प्लेक्सिटी: Difference between revisions

Namespaces

More

Page actions

Revision as of 10:56, 11 July 2023

Contents

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