कम्प्यूटेशनल कठोरता धारणा: Difference between revisions

Latest revision as of 09:43, 26 May 2023

कम्प्यूटेशनल जटिलता सिद्धांत में, कम्प्यूटेशनल कठोरता धारणा परिकल्पना है कि विशेष समस्या को कुशलतापूर्वक हल नहीं किया जा सकता है (जहां कुशलतापूर्वक "बहुपद समय में" का अर्थ है।) यह ज्ञात नहीं है कि अनिवार्य रूप से किसी उपयोगी समस्या के लिए (बिना नियम के) कठोरता को कैसे सिद्ध किया जाए। इसके अतिरिक्त, कंप्यूटर वैज्ञानिक नई या जटिल समस्या की कठोरता को समस्या के बारे में कम्प्यूटेशनल कठोरता धारणा से औपचारिक रूप से संबंधित करने के लिए कटौती पर विश्वास करते हैं जो उत्तम समझी जाती है।

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

कम्प्यूटेशनल कठोरता धारणाएँ एल्गोरिथम डिजाइनरों के मार्गदर्शन के लिए भी उपयोगी हैं: साधारण एल्गोरिथ्म अच्छी तरह से अध्ययन की गई कम्प्यूटेशनल कठोरता धारणा जैसे P ≠ NP का खंडन करने की संभावना नहीं है।

कठोरता धारणाओं की तुलना

कंप्यूटर वैज्ञानिकों के पास यह आकलन करने की विभिन्न विधियाँ हैं कि कौन सी कठोरता धारणा अधिक विश्वसनीय है।

कठोरता धारणाओं की शक्ति

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

औसत स्थिति के विपरीत सबसे खराब-स्थिति धारणायें

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

इसके अतिरिक्त, अतुलनीय समस्याओं के लिए भी, एक्सपोनेंशियल टाइम हाइपोथीसिस (ईटीएच) और वेरिएंट जैसी धारणा को अधिकांशतः प्लांटेड क्लिक अनुमान जैसी औसत-स्थिति धारणा के लिए उत्तम माना जाता है।^[1]

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

मिथ्याकरण

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

सामान्य क्रिप्टोग्राफ़िक कठोरता धारणाएँ

उपयोग में कई क्रिप्टोग्राफ़िक कठोरता धारणाएँ हैं। यह कुछ सबसे सामान्य धारणाओं की सूची है, और कुछ क्रिप्टोग्राफ़िक प्रोटोकॉल जो उनका उपयोग करते हैं।

पूर्णांक गुणनखंड

संयुक्त संख्या $n$ दी गई है, और विशेष रूप से एक जो दो बड़े अभाज्य $n=p\cdot q$ का गुणनफल है, पूर्णांक गुणनखंडन समस्या $p$ और $q$ का पता लगाने के लिए है (अधिक सामान्यतः, अभाज्य संख्या $p_{1},\dots ,p_{k}$ को खोजें जैसे कि $n=\prod _{i}p_{i}$ )। पूर्णांक गुणनखंडन के लिए एल्गोरिथ्म ढूंढने के लिए यह बड़ी विवृत समस्या है जो प्रतिनिधित्व के आकार ( $\log(n)$ ) में समय बहुपद में चलती है। कई क्रिप्टोग्राफ़िक प्रोटोकॉल की सुरक्षा इस धारणा पर निर्भर करती है कि पूर्णांक गुणनखंडन कठिन है (अर्थात बहुपद समय में हल नहीं किया जा सकता है)। क्रिप्टोप्रणाली जिनकी सुरक्षा इस धारणा के बराबर है, उनमें राबिन क्रिप्टोप्रणाली और ओकामोटो-उचियामा क्रिप्टोप्रणाली सम्मिलित हैं। कई और क्रिप्टोप्रणाली आरएसए, रेजिड्यूसिटी समस्या और फी-हाइडिंग जैसी कठोर धारणाओं पर विश्वास करते हैं।

आरएसए समस्या

संयुक्त संख्या $n$ , प्रतिपादक $e$ और संख्या $c:=m^{e}(\mathrm {mod} \;n)$ दी गई है, आरएसए समस्या $m$ का पता लगाने के लिए है। समस्या को कठिन माना जाता है, लेकिन इसका गुणनखंड $n$ दिया जाना सरल हो जाता है। आरएसए क्रिप्टोप्रणाली में, $(n,e)$ सार्वजनिक कुंजी है, $c$ संदेश $m$ का एन्क्रिप्शन है, और $n$ का गुणनखंडन डिक्रिप्शन के लिए उपयोग की जाने वाली गुप्त कुंजी है।

अवशिष्टता की समस्या

संयुक्त संख्या $n$ और पूर्णांक $y,d$ दिया गया है, अवशिष्टता समस्या यह निर्धारित करने के लिए है कि क्या $x$ उपस्थित है (वैकल्पिक रूप से, खोजें) ऐसा कि

x^{d}\equiv y{\pmod {n}}.

महत्वपूर्ण विशेष स्थितियों में द्विघात अवशिष्टता समस्या और निर्णायक संयुक्त अवशेषता धारणा सम्मिलित है। जैसा कि आरएसए की स्थिति में, इस समस्या (और इसकी विशेष स्थितियों) को कठिन माना जाता है, लेकिन $n$ के गुणनखंड को देखते हुए यह सरल हो जाता है। अवशिष्टता समस्याओं की कठोरता पर विश्वास करने वाले कुछ क्रिप्टो प्रणाली में सम्मिलित हैं:

गोल्डवेसर-मिकाली क्रिप्टोप्रणाली (द्विघात पुनर्वितरण समस्या)
ब्लम ब्लम शुब जनरेटर (द्विघात पुनर्वितरण समस्या)
पैलियर क्रिप्टोप्रणाली (निर्णायक संयुक्त अवशिष्टता समस्या)
बेनालोह क्रिप्टोप्रणाली (उच्च अवशिष्टता समस्या)
नाकाचे-स्टर्न क्रिप्टोप्रणाली (उच्च अवशिष्टता समस्या)

फी-छिपी धारणा

संयुक्त संख्या $m$ के लिए, यह ज्ञात नहीं है कि अपने यूलर के कुल फलन $\phi (m)$ की कुशलतापूर्वक गणना कैसे की जाए। फी-हाइडिंग की धारणा यह मानती है कि $\phi (m)$ की गणना करना कठिन है, और इसके अतिरिक्त $\phi (m)$ के किसी भी प्रमुख कारकों की गणना करना कठिन है। इस धारणा का उपयोग काचिन-मिकाली-स्टैडलर पीआईआर प्रोटोकॉल में किया जाता है।^[5]

असतत लॉग समस्या (डीएलपी)

समूह $G$ से दिए गए तत्व $a$ और $b$ , असतत लॉग समस्या पूर्णांक $k$ के लिए पूछती है जैसे कि $a=b^{k}$ । असतत लॉग समस्या को पूर्णांक गुणनखंडन के साथ तुलना करने के लिए नहीं जाना जाता है, लेकिन उनकी कम्प्यूटेशनल जटिलताएं निकट से संबंधित हैं।

असतत लॉग समस्या से संबंधित अधिकांश क्रिप्टोग्राफिक प्रोटोकॉल वास्तव में कठोर कम्प्यूटेशनल डिफी-हेलमैन धारणा पर विश्वास करते हैं: दिए गए समूह तत्वों $g,g^{a},g^{b}$ , जहाँ $g$ जनरेटर है और $a,b$ यादृच्छिक पूर्णांक हैं, इससे $g^{a\cdot b}$ ढूँढना कठिन है। इस धारणा का उपयोग करने वाले प्रोटोकॉल के उदाहरणों में मूल डिफी-हेलमैन कुंजी विनिमय, साथ ही साथ एलगामल एन्क्रिप्शन (जो अभी तक कठोर निर्णायक डिफी-हेलमैन (डीडीएच) संस्करण पर निर्भर करता है) सम्मिलित हैं।

बहुरेखीय मानचित्र

बहुरेखीय मानचित्र फलन $e:G_{1},\dots ,G_{n}\rightarrow G_{T}$ है, (जहाँ $G_{1},\dots ,G_{n},G_{T}$ समूह) ऐसे हैं कि हर किसी के लिए $g_{1},\dots ,g_{n}\in G_{1},\dots G_{n}$ और $a_{1},\dots ,a_{n}$ :

e(g_{1}^{a_{1}},\dots ,g_{n}^{a_{n}})=e(g_{1},\dots ,g_{n})^{a_{1}\cdots a_{n}}

क्रिप्टोग्राफ़िक अनुप्रयोगों के लिए, कोई समूह $G_{1},\dots ,G_{n},G_{T}$ और मानचित्र $e$ का निर्माण करना चाहेगा, जैसे कि मानचित्र और $G_{1},\dots ,G_{n},G_{T}$ पर समूह संचालन को कुशलता से गणना की जा सकती है, लेकिन $G_{1},\dots ,G_{n}$ पर असतत लॉग समस्या अभी भी कठिन है। कुछ अनुप्रयोगों के लिए मजबूत धारणाओं की आवश्यकता होती है, उदाहरण; डिफी-हेलमैन धारणाओं के बहुरेखीय अनुरूप।^[6]

$n=2$ की विशेष स्थिति के लिए, वील पेयरिंग और टेट पेयरिंग का उपयोग करके विश्वसनीय सुरक्षा के साथ द्विरेखीय मानचित्रों का निर्माण किया गया है।^[7] $n>2$ के लिए हाल के वर्षों में कई निर्माण प्रस्तावित किए गए हैं, लेकिन उनमें से कई टूट भी गए हैं, और वर्तमान में सुरक्षित प्रत्याशी के बारे में कोई सहमति नहीं है।^[8]

बहुरेखीय कठोरता धारणाओं पर विश्वास करने वाले कुछ क्रिप्टो प्रणाली में सम्मिलित हैं:

बोनेह-फ्रैंकलिन योजना (ब्लिनियर डिफी-हेलमैन)
बोनेह-लिन-शचम (ब्लिनियर डिफी-हेलमैन)
गर्ग-जेंट्री-हलेवी-रायकोवा-सहाय-वाटर्स अप्रभेद्यता अस्पष्टता और कार्यात्मक एन्क्रिप्शन के लिए प्रत्याशी (बहुरेखीय पहेली)^[9]

लैटिस की समस्या

लैटिस पर सबसे मौलिक कम्प्यूटेशनल समस्या है, सबसे छोटी सदिश समस्या (एसवीपी) है: लैटिस $L$ दी गई, $v\in L$ में सबसे लघु गैर-शून्य सदिश खोजें। अधिकांश क्रिप्टोप्रणाली को एसवीपी के रूपों पर कठोर धारणाओं की आवश्यकता होती है, जैसे कि लघुतम स्वतंत्र सदिश समस्या (एसआईवीपी), गैपएसवीपी,^[10] या अद्वितीय-एसवीपी।^[11]

क्रिप्टोग्राफी में सबसे उपयोगी लैटिस कठोरता धारणा सीखने के साथ त्रुटियों (एलडब्ल्यूई) समस्या के लिए है: दिए गए नमूने $(x,y)$ , जहाँ $y=f(x)$ कुछ रैखिक फलन $f(\cdot )$ के लिए, $f(\cdot )$ रैखिक बीजगणित का उपयोग करके यह सीखना सरल है। एलडब्ल्यूई समस्या में, एल्गोरिथम के इनपुट में त्रुटियाँ हैं, अर्थात प्रत्येक जोड़ी के लिए $y\neq f(x)$ कुछ छोटी संभावना के साथ है। माना जाता है कि त्रुटियां समस्या को असभ्य बनाती हैं (उचित मापदंडों के लिए); विशेष रूप से, एसवीपी के वेरिएंट से सबसे खराब स्थिति से लेकर औसत स्थिति तक की कमी ज्ञात करती है।^[12]

क्वांटम कंप्यूटरों के लिए, फैक्टरिंग और असतत लॉग समस्याएं सरल हैं, लेकिन लैटिस की समस्याओं को कठिन माना जाता है।^[13] यह कुछ लैटिस आधारित क्रिप्टोग्राफी को पोस्ट-क्वांटम क्रिप्टोग्राफी के लिए उपयुक्त बनाता है।

लैटिस समस्याओं की कठोरता पर विश्वास करने वाले कुछ क्रिप्टो प्रणाली में सम्मिलित हैं:

एनटीआरयू (एनटीआरयूएन्क्रिप्ट और एनटीआरयूसाइन दोनों)
पूरी तरह से होमोमोर्फिक एन्क्रिप्शन के लिए अधिकांश प्रत्याशी

गैर-क्रिप्टोग्राफ़िक कठोरता धारणाएँ

साथ ही उनके क्रिप्टोग्राफ़िक अनुप्रयोगों के साथ-साथ कठोरता धारणाओं का उपयोग कम्प्यूटेशनल जटिलता सिद्धांत में गणितीय उल्लेखों के प्रमाण प्रदान करने के लिए किया जाता है, जो बिना नियमों के प्रमाणित करना जटिल होता है। इन अनुप्रयोगों में, कोई यह प्रमाणित करता है कि कठोरता धारणा कुछ वांछित जटिलता-सैद्धांतिक कथन का अर्थ है, यह प्रमाणित करने के अतिरिक्त कि कथन स्वयं सत्य है। इस प्रकार की सबसे प्रसिद्ध धारणा यह है कि P ≠ NP, ^[14] लेकिन अन्य में घातीय समय परिकल्पना, प्लांटेड क्लिक धारणा, और अद्वितीय खेल धारणा सम्मिलित है।^[15]^[16]

सी-कठोर समस्याएं

कई सबसे खराब-स्थिति वाली कम्प्यूटेशनल समस्याओं को कुछ जटिलता वर्ग $C$ के लिए कठिन या पूर्ण होने के लिए जाना जाता है, विशेष रूप से एनपी-कठोरता (लेकिन अधिकांशतः पीएसपीएसीई-कठोर, पीपीएडी-कठोर आदि)। इसका अर्थ यह है कि वे वर्ग $C$ में किसी भी समस्या के रूप में कम से कम कठिन हैं। यदि कोई समस्या $C$ -कठोर है (बहुपद समय में कमी के संबंध में), तो इसे बहुपद-समय एल्गोरिदम द्वारा हल नहीं किया जा सकता है जब तक कि कम्प्यूटेशनल कठोरता धारणा $P\neq C$ असत्य है।

घातीय समय परिकल्पना (ईटीएच) और वेरिएंट्स

घातीय समय परिकल्पना (ईटीएच) $P\neq NP$ की कठोरता धारणाओं का सुदृढ़ीकरण है, जो अनुमान लगता है कि न केवल बूलियन संतुष्टि समस्या में बहुपद समय एल्गोरिथ्म नहीं है, बल्कि इसके लिए घातीय समय ( $2^{\Omega (n)}$ ) की भी आवश्यकता नही है।^[17] एक और भी कठोर धारणा, जिसे एक्सपोनेंशियल टाइम परिकल्पना (एसईटीएच) के रूप में जाना जाता है, यह अनुमान लगाती है कि $k$ -सैट को $2^{(1-\varepsilon _{k})n}$ समय की आवश्यकता होती है, जहाँ $\lim _{k\rightarrow \infty }\varepsilon _{k}=0$ है। ईटीएच, एसईटीएच, और संबंधित कम्प्यूटेशनल कठोरता धारणाएं सूक्ष्म जटिलता परिणामों को कम करने की अनुमति देती हैं, उदाहरण; परिणाम जो बहुपद समय और अर्ध-बहुपद समय में अंतर करते हैं,^[1] या यहाँ तक कि $n^{1.99}$ और $n^{2}$ पैरामीट्रिज्ड जटिलता में ऐसी धारणाएं भी उपयोगी होती हैं।^[18]^[19]

औसत-स्थिति कठोरता धारणा

कुछ कम्प्यूटेशनल समस्याओं को उदाहरणों के विशेष वितरण पर औसतन कठिन माना जाता है। उदाहरण के लिए, प्लांटेड क्लिक समस्या में, इनपुट यादृच्छिक ग्राफ नमूना है, एर्डोस-रेनी रैंडम ग्राफ का नमूना लेकर और फिर यादृच्छिक $k$ -क्लिक "रोपण", अर्थात् $k$ के समान रूप से यादृच्छिक नोड्स को जोड़ना (जहाँ $2\log _{2}n\ll k\ll {\sqrt {n}}$ ) और लक्ष्य प्लांटेड $k$ - क्लिक (जो अद्वितीय डब्ल्यू.एच.पी. है) को खोजना है।^[20] अन्य महत्वपूर्ण उदाहरण फीगे की परिकल्पना है, जो 3-एसएटी के यादृच्छिक उदाहरणों के बारे में कम्प्यूटेशनल कठोरता धारणा है (चरों के खंड के विशिष्ट अनुपात को बनाए रखने के लिए नमूना)।^[21] औसत-स्थिति कम्प्यूटेशनल कठोरता धारणाएँ आँकड़ों जैसे अनुप्रयोगों में औसत-स्थिति कठोरता को प्रमाणित करने के लिए उपयोगी होती हैं, जहाँ इनपुट पर प्राकृतिक वितरण होता है।^[22] इसके अतिरिक्त, प्लांटेड क्लिक कठोरता धारणा का उपयोग अन्य समस्याओं के बहुपद और अर्ध-बहुपद सबसे खराब समय जटिलता के बीच अंतर करने के लिए भी किया गया है,^[23] इसी तरह घातीय समय परिकल्पना के लिए भी किया गया है।

अद्वितीय खेल

अद्वितीय लेबल कवर समस्या, बाधा संतुष्टि समस्या है, जहां प्रत्येक बाधा $C$ में दो चर $x,y$ सम्मिलित हैं, और $x$ के प्रत्येक मान के लिए $y$ अद्वितीय मान है जो $C$ को संतुष्ट करता है। यह निर्धारित करना कि क्या सभी बाधाओं को पूरा किया जा सकता है, आसान है, लेकिन अद्वितीय खेल कंजेक्चर (यूजीसी) का मानना है कि यह निर्धारित करना कि क्या लगभग सभी बाधाएं ( $(1-\varepsilon )$ -अंश, किसी भी स्थिरांक के लिए $\varepsilon >0$ ) संतुष्ट हो सकते हैं या उनमें से कोई नहीं ( $\varepsilon$ -अंश) भी संतुष्ट किया जा सकता है, वे एनपी-कठोर है।^[16] सन्निकटन समस्याओं को अक्सर यूजीसी मानते हुए एनपी-कठोर के रूप में जाना जाता है; ऐसी समस्याओं को यूजी-कठोर कहा जाता है। विशेष रूप से, यह मानते हुए कि यूजीसी में अर्ध-निश्चित प्रोग्रामिंग एल्गोरिथम है जो कई महत्वपूर्ण समस्याओं के लिए इष्टतम सन्निकटन गारंटी प्राप्त करता है।^[24]

लघु सेट विस्तार

यूनिक लेबल कवर समस्या से निकटता से संबंधित है, लघु सेट विस्तार (एसएसई) समस्या: ग्राफ $G=(V,E)$ दिया गया, वर्टिकल का लघु सेट ( $n/\log(n)$ आकार का) खोजें; जिसका एज विस्तार न्यूनतम है। यह ज्ञात है कि यदि एसएसई का अनुमान लगाना कठिन है, तो अद्वितीय लेबल कवर भी ऐसा ही है। इसलिए, लघु सेट विस्तार परिकल्पना, जो मानती है कि एसएसई का अनुमान लगाना कठिन है, अद्वितीय खेल अनुमान की तुलना में कठोर (लेकिन निकटता से संबंधित) धारणा है।^[25] कुछ सन्निकटन समस्याओं को एसएसई-कठोर के रूप में जाना जाता है^[26] (अर्थात कम से कम उतना ही जटिल जितना अनुमानित एसएसई)।

3एसयूएम अनुमान

$n$ संख्याओं के सेट को देखते हुए, 3एसयूएम समस्या पूछती है कि क्या संख्याओं का त्रिक है, जिसका योग शून्य है। 3एसयूएम के लिए द्विघात-समय एल्गोरिथ्म है, और यह अनुमान लगाया गया है कि कोई भी एल्गोरिथ्म 3एसयूएम को "वास्तव में उप-द्विघात समय" में हल नहीं कर सकता है: 3एसयूएम अनुमान कम्प्यूटेशनल कठोरता धारणा है कि 3एसयूएम के लिए कोई $O(n^{2-\varepsilon })$ समय एल्गोरिदम नहीं हैं (किसी भी स्थिरांक के लिए $\varepsilon >0$ )। यह अनुमान कई समस्याओं के लिए निकट-द्विघात निचली सीमा को प्रमाणित करने के लिए उपयोगी है, अधिकतर कम्प्यूटेशनल ज्यामिति से उपयोगी है।^[27]

यह भी देखें

सुरक्षा स्तर

संदर्भ

↑ ^1.0 ^1.1 Braverman, Mark; Ko, Young Kun; Weinstein, Omri (2015). "Approximating the best Nash Equilibrium in $n^{o(\log(n))}$ -time breaks the Exponential Time Hypothesis". असतत एल्गोरिदम पर संगोष्ठी (सोडा). Society for Industrial and Applied Mathematics. pp. 970–982. doi:10.1137/1.9781611973730.66. ISBN 978-1-61197-374-7.
↑ J. Katz and Y. Lindell, Introduction to Modern Cryptography (Chapman and Hall/Crc Cryptography and Network Security Series), Chapman and Hall/CRC, 2007.
↑ Goldwasser, Shafi; Kalai, Yael Tauman (2016). "Cryptographic Assumptions: A Position Paper". Theory of Cryptography Conference (TCC) 2016. Springer. pp. 505–522. doi:10.1007/978-3-662-49096-9_21.
↑ Naor, Moni (2003). "On cryptographic assumptions and challenges". In Boneh, Dan (ed.). Advances in Cryptology – CRYPTO 2003: 23rd Annual International Cryptology Conference, Santa Barbara, California, USA, August 17-21, 2003, Proceedings. Lecture Notes in Computer Science. Vol. 2729. Berlin: Springer. pp. 96–109. doi:10.1007/978-3-540-45146-4_6. MR 2093188.
↑ Cachin, Christian; Micali, Silvio; Stadler, Markus (1999). Stern, Jacques (ed.). "बहुलघुगणक संचार के साथ कम्प्यूटेशनल रूप से निजी सूचना पुनर्प्राप्ति". Lecture Notes in Computer Science. Springer. 1592: 402–414. doi:10.1007/3-540-48910-X. ISBN 978-3-540-65889-4. S2CID 29690672.
↑ Boneh, Dan; Silverberg, Alice (2002). "Applications of Multilinear Forms to Cryptography". Cryptology ePrint Archive.
↑ Dutta, Ratna; Barua, Rana; Sarkar, Palash (2004). "Pairing-Based Cryptographic Protocols : A Survey". Cryptology ePrint Archive.
↑ Albrecht, Martin R. "Are Graded Encoding Scheme broken yet?". Retrieved 22 March 2018.
↑ Garg, Sanjam; Gentry, Craig; Halevi, Shai; Raykova, Mariana; Sahai, Amit; Waters, Brent (2016). "Candidate Indistinguishability Obfuscation and Functional Encryption for All Circuits" (PDF). SIAM Journal on Computing. SIAM. 45 (3): 882–929. doi:10.1137/14095772X.
↑ Peikert, Chris (2009). "Public-key cryptosystems from the worst-case shortest vector problem: extended abstract". Proceedings on 41st Annual ACM Symposium on Theory of Computing (STOC). pp. 333–342. doi:10.1145/1536414.1536461.
↑ Ajtai, Miklós; Dwork, Cynthia (1997). "A Public-Key Cryptosystem with Worst-Case/Average-Case Equivalence". Proceedings on 29th Annual ACM Symposium on Theory of Computing (STOC). pp. 284–293. doi:10.1145/258533.258604.
↑ Regev, Oded (2010). "The Learning with Errors Problem (Invited Survey)". Conference on Computational Complexity (CCC) 2010. pp. 191–204. doi:10.1109/CCC.2010.26.
↑ Peikert, Chris (2016). "जाली क्रिप्टोग्राफी का एक दशक". Foundations and Trends in Theoretical Computer Science. 10 (4): 283–424. doi:10.1561/0400000074.
↑ Fortnow, Lance (2009). "पी बनाम एनपी समस्या की स्थिति" (PDF). Communications of the ACM. 52 (9): 78–86. doi:10.1145/1562164.1562186. S2CID 5969255. Archived from the original (PDF) on 2011-02-24..
↑ Woeginger, Gerhard (2003). "Exact algorithms for NP-hard problems: A survey". Combinatorial Optimization — Eureka, You Shrink!. Vol. 2570. Springer-Verlag. pp. 185–207. doi:10.1007/3-540-36478-1_17..
↑ ^16.0 ^16.1 Khot, Subhash (2010). "On the Unique Games Conjecture". Proc. 25th IEEE Conference on Computational Complexity (PDF). pp. 99–121. doi:10.1109/CCC.2010.19..
↑ Impagliazzo, Russell; Paturi, Ramamohan (1999). "The Complexity of k-SAT". Proc. 14th IEEE Conf. on Computational Complexity. pp. 237–240. doi:10.1109/CCC.1999.766282.
↑ Abboud, Amir; Vassilevska-Williams, Virginia; Weimann, Oren (2014). "Consequences of Faster Alignment of Sequences". Automata, Languages, and Programming - 41st International Colloquium, ICALP 2014. pp. 39–51. doi:10.1007/978-3-662-43948-7_4.
↑ Lokshtanov, Daniel; Marx, Daniel; Saurabh, Saket (2011). "Lower bounds based on the Exponential Time Hypothesis". Bulletin of the EATCS. 105: 41–72.
↑ Arora, Sanjeev; Barak, Boaz (2009). Computational Complexity: A Modern Approach. Cambridge University Press. pp. 362–363. ISBN 9780521424264..
↑ Feige, Uriel (2002). "Relations between average case complexity and approximation complexity". Proceedings on 34th Annual ACM Symposium on Theory of Computing (STOC). pp. 534–543. doi:10.1145/509907.509985.
↑ Berthet, Quentin; Rigollet, Philippe (2013). "Complexity Theoretic Lower Bounds for Sparse Principal Component Detection". COLT 2013. pp. 1046–1066.
↑ Hazan, Elad; Krauthgamer, Robert (2011). "How Hard Is It to Approximate the Best Nash Equilibrium?". SIAM Journal on Computing. 40 (1): 79–91. CiteSeerX 10.1.1.139.7326. doi:10.1137/090766991.
↑ Raghavendra, Prasad (2008). "Optimal algorithms and inapproximability results for every CSP?". 40th Annual ACM Symposium on theory of Computing (STOC) 2008. pp. 245–254. doi:10.1145/1374376.1374414.
↑ Raghavendra, Prasad; Steurer, David (2010). "Graph Expansion and the Unique Games Conjecture". 42nd Annual ACM Symposium on theory of Computing (STOC) 2010. pp. 755–764. doi:10.1145/1806689.1806792.
↑ Wu, Yu; Austrin, Per; Pitassi, Toniann; Liu, David (2014). "Inapproximability of Treewidth and Related Problems". Journal of Artificial Intelligence Research. 49: 569–600. doi:10.1613/jair.4030.
↑ Vassilevska Williams, Virginia (2018). "On some fine-grained questions in algorithms and complexity". ICM 2018 (PDF).

[BKW15-1] 1.0 ^1.1 Braverman, Mark; Ko, Young Kun; Weinstein, Omri (2015). "Approximating the best Nash Equilibrium in $n^{o(\log(n))}$ -time breaks the Exponential Time Hypothesis". असतत एल्गोरिदम पर संगोष्ठी (सोडा). Society for Industrial and Applied Mathematics. pp. 970–982. doi:10.1137/1.9781611973730.66. ISBN 978-1-61197-374-7.

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

[GK16-3] Goldwasser, Shafi; Kalai, Yael Tauman (2016). "Cryptographic Assumptions: A Position Paper". Theory of Cryptography Conference (TCC) 2016. Springer. pp. 505–522. doi:10.1007/978-3-662-49096-9_21.

[4] Naor, Moni (2003). "On cryptographic assumptions and challenges". In Boneh, Dan (ed.). Advances in Cryptology – CRYPTO 2003: 23rd Annual International Cryptology Conference, Santa Barbara, California, USA, August 17-21, 2003, Proceedings. Lecture Notes in Computer Science. Vol. 2729. Berlin: Springer. pp. 96–109. doi:10.1007/978-3-540-45146-4_6. MR 2093188.

[5] Cachin, Christian; Micali, Silvio; Stadler, Markus (1999). Stern, Jacques (ed.). "बहुलघुगणक संचार के साथ कम्प्यूटेशनल रूप से निजी सूचना पुनर्प्राप्ति". Lecture Notes in Computer Science. Springer. 1592: 402–414. doi:10.1007/3-540-48910-X. ISBN 978-3-540-65889-4. S2CID 29690672.

[BS02-6] Boneh, Dan; Silverberg, Alice (2002). "Applications of Multilinear Forms to Cryptography". Cryptology ePrint Archive.

[DBS04-7] Dutta, Ratna; Barua, Rana; Sarkar, Palash (2004). "Pairing-Based Cryptographic Protocols : A Survey". Cryptology ePrint Archive.

[8] Albrecht, Martin R. "Are Graded Encoding Scheme broken yet?". Retrieved 22 March 2018.

[9] Garg, Sanjam; Gentry, Craig; Halevi, Shai; Raykova, Mariana; Sahai, Amit; Waters, Brent (2016). "Candidate Indistinguishability Obfuscation and Functional Encryption for All Circuits" (PDF). SIAM Journal on Computing. SIAM. 45 (3): 882–929. doi:10.1137/14095772X.

[peikert09-10] Peikert, Chris (2009). "Public-key cryptosystems from the worst-case shortest vector problem: extended abstract". Proceedings on 41st Annual ACM Symposium on Theory of Computing (STOC). pp. 333–342. doi:10.1145/1536414.1536461.

[ad97-11] Ajtai, Miklós; Dwork, Cynthia (1997). "A Public-Key Cryptosystem with Worst-Case/Average-Case Equivalence". Proceedings on 29th Annual ACM Symposium on Theory of Computing (STOC). pp. 284–293. doi:10.1145/258533.258604.

[regev10-12] Regev, Oded (2010). "The Learning with Errors Problem (Invited Survey)". Conference on Computational Complexity (CCC) 2010. pp. 191–204. doi:10.1109/CCC.2010.26.

[peikert16-13] Peikert, Chris (2016). "जाली क्रिप्टोग्राफी का एक दशक". Foundations and Trends in Theoretical Computer Science. 10 (4): 283–424. doi:10.1561/0400000074.

[14] Fortnow, Lance (2009). "पी बनाम एनपी समस्या की स्थिति" (PDF). Communications of the ACM. 52 (9): 78–86. doi:10.1145/1562164.1562186. S2CID 5969255. Archived from the original (PDF) on 2011-02-24..

[15] Woeginger, Gerhard (2003). "Exact algorithms for NP-hard problems: A survey". Combinatorial Optimization — Eureka, You Shrink!. Vol. 2570. Springer-Verlag. pp. 185–207. doi:10.1007/3-540-36478-1_17..

[khot10-16] 16.0 ^16.1 Khot, Subhash (2010). "On the Unique Games Conjecture". Proc. 25th IEEE Conference on Computational Complexity (PDF). pp. 99–121. doi:10.1109/CCC.2010.19..

[17] Impagliazzo, Russell; Paturi, Ramamohan (1999). "The Complexity of k-SAT". Proc. 14th IEEE Conf. on Computational Complexity. pp. 237–240. doi:10.1109/CCC.1999.766282.

[18] Abboud, Amir; Vassilevska-Williams, Virginia; Weimann, Oren (2014). "Consequences of Faster Alignment of Sequences". Automata, Languages, and Programming - 41st International Colloquium, ICALP 2014. pp. 39–51. doi:10.1007/978-3-662-43948-7_4.

[LMS11-19] Lokshtanov, Daniel; Marx, Daniel; Saurabh, Saket (2011). "Lower bounds based on the Exponential Time Hypothesis". Bulletin of the EATCS. 105: 41–72.

[ab-20] Arora, Sanjeev; Barak, Boaz (2009). Computational Complexity: A Modern Approach. Cambridge University Press. pp. 362–363. ISBN 9780521424264..

[Feige02-21] Feige, Uriel (2002). "Relations between average case complexity and approximation complexity". Proceedings on 34th Annual ACM Symposium on Theory of Computing (STOC). pp. 534–543. doi:10.1145/509907.509985.

[BR13-22] Berthet, Quentin; Rigollet, Philippe (2013). "Complexity Theoretic Lower Bounds for Sparse Principal Component Detection". COLT 2013. pp. 1046–1066.

[HK11-23] Hazan, Elad; Krauthgamer, Robert (2011). "How Hard Is It to Approximate the Best Nash Equilibrium?". SIAM Journal on Computing. 40 (1): 79–91. CiteSeerX 10.1.1.139.7326. doi:10.1137/090766991.

[rag08-24] Raghavendra, Prasad (2008). "Optimal algorithms and inapproximability results for every CSP?". 40th Annual ACM Symposium on theory of Computing (STOC) 2008. pp. 245–254. doi:10.1145/1374376.1374414.

[rs10-25] Raghavendra, Prasad; Steurer, David (2010). "Graph Expansion and the Unique Games Conjecture". 42nd Annual ACM Symposium on theory of Computing (STOC) 2010. pp. 755–764. doi:10.1145/1806689.1806792.

[26] Wu, Yu; Austrin, Per; Pitassi, Toniann; Liu, David (2014). "Inapproximability of Treewidth and Related Problems". Journal of Artificial Intelligence Research. 49: 569–600. doi:10.1613/jair.4030.

[27] Vassilevska Williams, Virginia (2018). "On some fine-grained questions in algorithms and complexity". ICM 2018 (PDF).

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]

[21]

[22]

[23]

[24]

[25]

[26]

[27]

v t e कम्प्यूटेशनल कठोरता धारणाएं
संख्या सिद्धांत	पूर्णांक कारक फी-छिपा आरएसए समस्या मजबूत आरएसए द्विघात अवशेष निर्णायक समग्र अवशेष उच्च अवशेष
समूह सिद्धांत	असतत लॉगरिथम डिफी-हेलमैन निर्णायक डिफी -हेलमैन कम्प्यूटेशनल डिफी -हेलमैन
जोड़ियां	बाहरी diffie -hellman उप-समूह छिपा हुआ निर्णय रैखिक
जाली	सबसे छोटा वेक्टर समस्या निकटतम वेक्टर समस्या ( GAP त्रुटियों के साथ सीखना त्रुटियों के साथ रिंग सीखना लघु पूर्णांक समाधान
गैर-क्रिप्टोग्राफ़िक	घातीय समय परिकल्पना अद्वितीय खेल अनुमान लगाए गए क्लिक कॉनजेक्चर

Anonymous

Search

कम्प्यूटेशनल कठोरता धारणा: Difference between revisions

Namespaces

More

Page actions

Latest revision as of 09:43, 26 May 2023

Contents

कठोरता धारणाओं की तुलना

कठोरता धारणाओं की शक्ति

औसत स्थिति के विपरीत सबसे खराब-स्थिति धारणायें

मिथ्याकरण

सामान्य क्रिप्टोग्राफ़िक कठोरता धारणाएँ

पूर्णांक गुणनखंड

आरएसए समस्या

अवशिष्टता की समस्या

फी-छिपी धारणा

असतत लॉग समस्या (डीएलपी)

बहुरेखीय मानचित्र

लैटिस की समस्या

गैर-क्रिप्टोग्राफ़िक कठोरता धारणाएँ

सी-कठोर समस्याएं

घातीय समय परिकल्पना (ईटीएच) और वेरिएंट्स

औसत-स्थिति कठोरता धारणा

अद्वितीय खेल

लघु सेट विस्तार

3एसयूएम अनुमान

यह भी देखें

संदर्भ

Navigation

Navigation

Wiki tools

Wiki tools

@@ Line 1: / Line 1: @@
 {{short description|Hypothesis in computational complexity theory}}
-[[कम्प्यूटेशनल जटिलता सिद्धांत]] में, एक कम्प्यूटेशनल कठोरता धारणा परिकल्पना है कि एक विशेष समस्या को कुशलतापूर्वक हल नहीं किया जा सकता है (जहां 'कुशलता' का अर्थ आमतौर पर बहुपद समय में होता है)। यह ज्ञात नहीं है कि अनिवार्य रूप से किसी उपयोगी समस्या के लिए (बिना शर्त) कठोरता को कैसे सिद्ध किया जाए। इसके बजाय, कंप्यूटर वैज्ञानिक एक नई या जटिल समस्या की कठोरता को औपचारिक रूप से किसी समस्या के बारे में कम्प्यूटेशनल कठोरता धारणा से संबंधित करने के लिए रिडक्शन (जटिलता) पर भरोसा करते हैं जो बेहतर समझी जाती है।
+[[कम्प्यूटेशनल जटिलता सिद्धांत]] में, कम्प्यूटेशनल कठोरता धारणा परिकल्पना है कि विशेष समस्या को कुशलतापूर्वक हल नहीं किया जा सकता है (जहां कुशलतापूर्वक "बहुपद समय में" का अर्थ है।) यह ज्ञात नहीं है कि अनिवार्य रूप से किसी उपयोगी समस्या के लिए (बिना नियम के) कठोरता को कैसे सिद्ध किया जाए। इसके अतिरिक्त, कंप्यूटर वैज्ञानिक नई या जटिल समस्या की कठोरता को समस्या के बारे में कम्प्यूटेशनल कठोरता धारणा से औपचारिक रूप से संबंधित करने के लिए कटौती पर विश्वास करते हैं जो उत्तम समझी जाती है।
-[[क्रिप्टोग्राफी]] में कम्प्यूटेशनल कठोरता मान्यताओं का विशेष महत्व है। क्रिप्टोग्राफ़ी में एक प्रमुख लक्ष्य क्रिप्टोग्राफ़िक आदिमों को साबित करने योग्य सुरक्षा के साथ बनाना है। कुछ मामलों में, [[क्रिप्टोग्राफिक आदिम]] में [[सूचना सैद्धांतिक सुरक्षा]] पाई जाती है; वन-टाइम पैड एक सामान्य उदाहरण है। हालाँकि, सूचना सिद्धांत सुरक्षा हमेशा प्राप्त नहीं की जा सकती है; ऐसे मामलों में, क्रिप्टोग्राफ़र कम्प्यूटेशनल सुरक्षा में वापस आ जाते हैं। मोटे तौर पर, इसका मतलब यह है कि ये सिस्टम सुरक्षित हैं ''यह मानते हुए कि कोई भी विरोधी कम्प्यूटेशनल रूप से सीमित हैं'', क्योंकि सभी विरोधी व्यवहार में हैं।
+[[क्रिप्टोग्राफी]] में कम्प्यूटेशनल कठोरता धारणाओं का विशेष महत्व है। क्रिप्टोग्राफ़ी में प्रमुख लक्ष्य क्रिप्टोग्राफ़िक प्रिमिटिव को प्रमाणित करने योग्य सुरक्षा के साथ बनाना है। कुछ स्थितियों में, [[क्रिप्टोग्राफिक आदिम|क्रिप्टोग्राफिक प्रोटोकॉल]] में [[सूचना सैद्धांतिक सुरक्षा]] पाई जाती है; जिसका वन-टाइम पैड सामान्य उदाहरण है। चूँकि, सूचना सिद्धांत सुरक्षा सदैव प्राप्त नहीं की जा सकती है; ऐसी स्थितियों में, क्रिप्टोग्राफ़र कम्प्यूटेशनल सुरक्षा में वापस आ जाते हैं। सामान्यता, इसका अर्थ यह है कि ये प्रणालियां सुरक्षित हैं यह मानते हुए कि कोई भी विरोधी कम्प्यूटेशनल रूप से सीमित हैं, क्योंकि सभी विरोधी अभ्यास कर रहे हैं।
-कम्प्यूटेशनल कठोरता धारणाएँ एल्गोरिथम डिजाइनरों के मार्गदर्शन के लिए भी उपयोगी हैं: एक साधारण एल्गोरिथ्म एक अच्छी तरह से अध्ययन की गई कम्प्यूटेशनल कठोरता धारणा का खंडन करने की संभावना नहीं है जैसे कि पी बनाम एनपी समस्या | पी ≠ एनपी।
+कम्प्यूटेशनल कठोरता धारणाएँ एल्गोरिथम डिजाइनरों के मार्गदर्शन के लिए भी उपयोगी हैं: साधारण एल्गोरिथ्म अच्छी तरह से अध्ययन की गई कम्प्यूटेशनल कठोरता धारणा जैसे [[P ≠ NP]] का खंडन करने की संभावना नहीं है।
-== कठोरता मान्यताओं की तुलना ==
+== कठोरता धारणाओं की तुलना ==
-कंप्यूटर वैज्ञानिकों के पास यह आकलन करने के विभिन्न तरीके हैं कि कौन सी कठोरता धारणा अधिक विश्वसनीय है।
+कंप्यूटर वैज्ञानिकों के पास यह आकलन करने की विभिन्न विधियाँ हैं कि कौन सी कठोरता धारणा अधिक विश्वसनीय है।
-=== कठोरता मान्यताओं की ताकत ===
+=== कठोरता धारणाओं की शक्ति ===
-हम कहते हैं कि धारणा <math>A</math> धारणा से ज्यादा मजबूत है <math>B</math> कब <math>A</math> तात्पर्य <math>B</math> (और बातचीत गलत है या ज्ञात नहीं है)।
+हम कहते हैं कि धारणा <math>A</math> धारणा <math>B</math> से अधिक कठोर है जब <math>A</math> का तात्पर्य <math>B</math> से है (और इसका व्युत्क्रम असत्य है या ज्ञात नहीं है)। दूसरे शब्दों में, तथापि धारणा <math>A</math> असत्य थी, परन्तु धारणा <math>B</math> अभी भी सच हो सकती है, और क्रिप्टोग्राफ़िक प्रोटोकॉल धारणा <math>B</math> के आधार पर अभी भी उपयोग करने के लिए सुरक्षित हो सकता है। इस प्रकार क्रिप्टोग्राफ़िक प्रोटोकॉल तैयार करते समय, सबसे अशक्त संभावित धारणाओं का उपयोग करके सुरक्षा को प्रमाणित करने में सक्षम होने की आशा रहती है।
-दूसरे शब्दों में, भले ही धारणा <math>A</math> झूठे थे, धारणा <math>B</math> अभी भी सच हो सकता है, और क्रिप्टोग्राफ़िक प्रोटोकॉल धारणा के आधार पर <math>B</math> अभी भी उपयोग करने के लिए सुरक्षित हो सकता है।
-इस प्रकार क्रिप्टोग्राफ़िक प्रोटोकॉल तैयार करते समय, सबसे कमजोर संभावित धारणाओं का उपयोग करके सुरक्षा को साबित करने में सक्षम होने की उम्मीद है।
+===औसत स्थिति के विपरीत सबसे खराब-स्थिति धारणायें ===
+{{See also|सबसे अच्छी, सबसे खराब और औसत स्थिति}}
+औसत-स्थिति धारणा कहती है कि कुछ स्पष्ट वितरण से अधिकांश उदाहरणों पर विशिष्ट समस्या कठिन है, जबकि सबसे खराब-स्थिति धारणा केवल यह कहती है कि समस्या कुछ उदाहरणों पर कठिन है। किसी समस्या के लिए, औसत-स्थिति की कठोरता का तात्पर्य सबसे खराब-कठोरता से है, इसलिए औसत-स्थिति की कठोरता धारणा एक ही समस्या के लिए सबसे खराब-कठोरता धारणा से अधिक कठोर है।
+इसके अतिरिक्त, अतुलनीय समस्याओं के लिए भी, एक्सपोनेंशियल टाइम हाइपोथीसिस (ईटीएच) और वेरिएंट जैसी धारणा को अधिकांशतः [[ लगाया गुट |प्लांटेड क्लिक]] अनुमान जैसी औसत-स्थिति धारणा के लिए उत्तम माना जाता है।<ref name="BKW15">{{cite conference|doi = 10.1137/1.9781611973730.66|ISBN = 978-1-61197-374-7|contribution = Approximating the best Nash Equilibrium in <math>n^{o(\log(n))}</math>-time breaks the Exponential Time Hypothesis|title = असतत एल्गोरिदम पर संगोष्ठी (सोडा)|pages = 970–982|year = 2015|author1-link = Mark Braverman (mathematician)|first1=Mark|last1= Braverman| first2 = Young Kun|last2=Ko| first3 = Omri|last3=Weinstein| publisher = [[Society for Industrial and Applied Mathematics]]}}</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="GK16">{{cite conference|doi = 10.1007/978-3-662-49096-9_21|contribution = Cryptographic Assumptions: A Position Paper|title = Theory of Cryptography Conference (TCC) 2016|pages = 505–522|year = 2016|author1-link = Shafi Goldwasser|first1=Shafi|last1=Goldwasser| author2-link= Yael Tauman Kalai|first2=Yael Tauman|last2=Kalai|publisher = Springer|title-link = Theory of Cryptography Conference|doi-access = free}}</ref>
-===औसत-मामला बनाम सबसे खराब-मामला मान्यताओं===
-{{See also|Best, worst and average case}}
-एक औसत-केस जटिलता|औसत-केस धारणा कहती है कि कुछ स्पष्ट वितरण से अधिकांश उदाहरणों पर एक विशिष्ट समस्या कठिन है, जबकि सबसे खराब-केस जटिलता|सबसे खराब-केस धारणा केवल यह कहती है कि समस्या कुछ उदाहरणों पर कठिन है। किसी समस्या के लिए, औसत-मामले की कठोरता का तात्पर्य सबसे खराब-कठोरता से है, इसलिए एक #औसत-मामले की कठोरता धारणा|औसत-मामले की कठोरता धारणा एक ही समस्या के लिए सबसे खराब-कठोरता धारणा से अधिक मजबूत है।
-इसके अलावा, अतुलनीय समस्याओं के लिए भी, #Exponential Time Hypothesis (ETH) और वेरिएंट जैसी धारणा को अक्सर माना जाता है
-[[ लगाया गुट ]] की तरह #औसत-मामले की कठोरता धारणा|औसत-मामले की धारणा के लिए बेहतर।<ref name=BKW15>{{cite conference|doi = 10.1137/1.9781611973730.66|ISBN = 978-1-61197-374-7|contribution = Approximating the best Nash Equilibrium in <math>n^{o(\log(n))}</math>-time breaks the Exponential Time Hypothesis|title = असतत एल्गोरिदम पर संगोष्ठी (सोडा)|pages = 970–982|year = 2015|author1-link = Mark Braverman (mathematician)|first1=Mark|last1= Braverman| first2 = Young Kun|last2=Ko| first3 = Omri|last3=Weinstein| publisher = [[Society for Industrial and Applied Mathematics]]}}</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> सौभाग्य से, क्रिप्टोग्राफी में उपयोग की जाने वाली कई औसत-केस धारणाएं (#RSA समस्या, #डिस्क्रीट लॉग समस्या (DLP) और कुछ #Lattice समस्याओं सहित) सबसे खराब-केस-से-औसत-केस कटौती के माध्यम से सबसे खराब-केस धारणाओं पर आधारित हो सकती हैं।<ref name=GK16>{{cite conference|doi = 10.1007/978-3-662-49096-9_21|contribution = Cryptographic Assumptions: A Position Paper|title = Theory of Cryptography Conference (TCC) 2016|pages = 505–522|year = 2016|author1-link = Shafi Goldwasser|first1=Shafi|last1=Goldwasser| author2-link= Yael Tauman Kalai|first2=Yael Tauman|last2=Kalai|publisher = Springer|title-link = Theory of Cryptography Conference|doi-access = free}}</ref>
 === [[मिथ्याकरण]] ===
-कम्प्यूटेशनल कठोरता धारणा की एक वांछित विशेषता मिथ्याकरण है, अर्थात यदि धारणा झूठी थी, तो इसे साबित करना संभव होगा।
+कम्प्यूटेशनल कठोरता धारणा की वांछित विशेषता मिथ्याकरण है, अर्थात यदि धारणा असत्य थी, तो इसे प्रमाणित करना संभव होगा। विशेष रूप से, {{harvtxt|नौर|2003}} ने क्रिप्टोग्राफ़िक मिथ्याकरण की औपचारिक धारणा प्रस्तुत की थी।<ref>{{cite conference
-विशेष रूप से, {{harvtxt|Naor|2003}} ने क्रिप्टोग्राफ़िक मिथ्याकरण की एक औपचारिक धारणा पेश की।<ref>{{cite conference
   | last = Naor | first = Moni
   | editor-last = Boneh | editor-first = Dan
@@ Line 37: / Line 37: @@
   | volume = 2729
   | year = 2003| doi-access = free
-  }}</ref>
+  }}</ref> सामान्यता, यदि कम्प्यूटेशनल कठोरता धारणा को चुनौती के रूप में तैयार किया जा सकता है ,तो इसे अनुचित माना जाता है: विरोधी और कुशल सत्यापनकर्ता के बीच इंटरैक्टिव प्रोटोकॉल रहता है, जहां कुशल विरोधी सत्यापनकर्ता को यह स्वीकार करने के लिए सहमत कर सकता है यदि और केवल यदि धारणा अनुचित है।
-मोटे तौर पर, एक कम्प्यूटेशनल कठोरता धारणा को गलत माना जाता है अगर इसे चुनौती के रूप में तैयार किया जा सकता है:
-एक विरोधी और एक कुशल सत्यापनकर्ता के बीच एक इंटरैक्टिव प्रोटोकॉल,
-जहां एक कुशल विरोधी सत्यापनकर्ता को स्वीकार करने के लिए राजी कर सकता है अगर और केवल अगर धारणा गलत है।
 == सामान्य क्रिप्टोग्राफ़िक कठोरता धारणाएँ ==
-उपयोग में कई क्रिप्टोग्राफ़िक कठोरता धारणाएँ हैं। यह कुछ सबसे आम लोगों की सूची है, और कुछ क्रिप्टोग्राफ़िक प्रोटोकॉल जो उनका उपयोग करते हैं।
+उपयोग में कई क्रिप्टोग्राफ़िक कठोरता धारणाएँ हैं। यह कुछ सबसे सामान्य धारणाओं की सूची है, और कुछ क्रिप्टोग्राफ़िक प्रोटोकॉल जो उनका उपयोग करते हैं।
 === पूर्णांक गुणनखंड ===
-{{Main|Integer factorization}}
+{{Main|पूर्णांक गुणनखंडन}}
-एक [[समग्र संख्या]] दी गई है <math>n</math>, और विशेष रूप से एक जो दो बड़े प्राइम्स का उत्पाद है <math>n = p\cdot q</math>, पूर्णांक गुणनखंडन समस्या का पता लगाना है <math>p</math> और <math>q</math> (अधिक आम तौर पर, प्राइम खोजें <math>p_1,\dots,p_k</math> ऐसा है कि <math>n = \prod_i p_i</math>).
+[[समग्र संख्या|संयुक्त संख्या]] <math>n</math> दी गई है, और विशेष रूप से एक जो दो बड़े अभाज्य <math>n = p\cdot q</math> का गुणनफल है, पूर्णांक गुणनखंडन समस्या <math>p</math> और <math>q</math> का पता लगाने के लिए है (अधिक सामान्यतः, अभाज्य संख्या <math>p_1,\dots,p_k</math> को खोजें जैसे कि <math>n = \prod_i p_i</math>)। पूर्णांक गुणनखंडन के लिए एल्गोरिथ्म ढूंढने के लिए यह बड़ी विवृत समस्या है जो प्रतिनिधित्व के आकार (<math>\log(n)</math>) में समय बहुपद में चलती है। कई क्रिप्टोग्राफ़िक प्रोटोकॉल की सुरक्षा इस धारणा पर निर्भर करती है कि पूर्णांक गुणनखंडन कठिन है (अर्थात बहुपद समय में हल नहीं किया जा सकता है)। क्रिप्टोप्रणाली जिनकी सुरक्षा इस धारणा के बराबर है, उनमें [[राबिन क्रिप्टोसिस्टम|राबिन क्रिप्टोप्रणाली]] और ओकामोटो-उचियामा क्रिप्टोप्रणाली सम्मिलित हैं। कई और क्रिप्टोप्रणाली आरएसए, रेजिड्यूसिटी समस्या और फी-हाइडिंग जैसी कठोर धारणाओं पर विश्वास करते हैं।
-पूर्णांक गुणनखंडन के लिए एक एल्गोरिथ्म खोजने के लिए यह एक बड़ी खुली समस्या है जो प्रतिनिधित्व के आकार में समय बहुपद में चलती है (<math>\log(n)</math>).
-कई क्रिप्टोग्राफ़िक प्रोटोकॉल की सुरक्षा इस धारणा पर निर्भर करती है कि पूर्णांक गुणनखंडन कठिन है (अर्थात बहुपद समय में हल नहीं किया जा सकता है)।
-क्रिप्टोसिस्टम जिनकी सुरक्षा इस धारणा के बराबर है, में [[राबिन क्रिप्टोसिस्टम]] और ओकामोटो-उचियामा क्रिप्टोसिस्टम शामिल हैं।
-कई और क्रिप्टोसिस्टम मजबूत धारणाओं पर भरोसा करते हैं जैसे #RSA समस्या, #अवशेष समस्याएं, और #Phi-hiding धारणा|Phi-hiding।
 ==== आरएसए समस्या ====
-  {{Main|RSA problem}}
+  {{Main|आरएसए समस्या}}
-एक समग्र संख्या दी गई है <math>n</math>, प्रतिपादक <math>e</math> और संख्या <math>c := m^e (\mathrm{mod}\; n)</math>, RSA समस्या का पता लगाना है <math>m</math>.
+संयुक्त संख्या <math>n</math>, प्रतिपादक <math>e</math> और संख्या <math>c := m^e (\mathrm{mod}\; n)</math> दी गई है, आरएसए समस्या <math>m</math> का पता लगाने के लिए है। समस्या को कठिन माना जाता है, लेकिन इसका गुणनखंड <math>n</math> दिया जाना सरल हो जाता है। [[आरएसए क्रिप्टोसिस्टम|आरएसए क्रिप्टोप्रणाली]] में, <math>(n,e)</math> [[सार्वजनिक कुंजी क्रिप्टोग्राफी|सार्वजनिक कुंजी]] है, <math>c</math> संदेश <math>m</math> का एन्क्रिप्शन है, और <math>n</math> का गुणनखंडन डिक्रिप्शन के लिए उपयोग की जाने वाली गुप्त कुंजी है।
-समस्या को कठिन माना जाता है, लेकिन इसका गुणनखंड दिया जाना आसान हो जाता है <math>n</math>.
-[[आरएसए क्रिप्टोसिस्टम]] में, <math>(n,e)</math> [[सार्वजनिक कुंजी क्रिप्टोग्राफी]] है, <math>c</math> संदेश का एन्क्रिप्शन है <math>m</math>, और का गुणनखंडन <math>n</math> डिक्रिप्शन के लिए उपयोग की जाने वाली गुप्त कुंजी है।
 ==== अवशिष्टता की समस्या ====
-{{Main|Higher residuosity problem}}
+{{Main|उच्च अवशेषता समस्या}}
-एक समग्र संख्या दी गई है <math>n</math> और पूर्णांक <math>y,d</math>, अवशिष्टता समस्या यह निर्धारित करने के लिए है कि क्या मौजूद है (वैकल्पिक रूप से, खोजें) <math>x</math> ऐसा है कि
+संयुक्त संख्या <math>n</math> और पूर्णांक <math>y,d</math> दिया गया है, अवशिष्टता समस्या यह निर्धारित करने के लिए है कि क्या <math>x</math> उपस्थित है (वैकल्पिक रूप से, खोजें) ऐसा कि
 :<math> x^d \equiv y \pmod{n}.</math>
-महत्वपूर्ण विशेष मामलों में [[द्विघात अवशिष्टता समस्या]] और निर्णायक समग्र अवशेषता धारणा शामिल है।
+महत्वपूर्ण विशेष स्थितियों में [[द्विघात अवशिष्टता समस्या]] और निर्णायक संयुक्त अवशेषता धारणा सम्मिलित है। जैसा कि आरएसए की स्थिति में, इस समस्या (और इसकी विशेष स्थितियों) को कठिन माना जाता है, लेकिन <math>n</math> के गुणनखंड को देखते हुए यह सरल हो जाता है। अवशिष्टता समस्याओं की कठोरता पर विश्वास करने वाले कुछ क्रिप्टो प्रणाली में सम्मिलित हैं:
-जैसा कि आरएसए के मामले में, इस समस्या (और इसके विशेष मामलों) को कठिन होने का अनुमान लगाया गया है, लेकिन इसके गुणनखंड को देखते हुए यह आसान हो गया है <math>n</math>.
+*गोल्डवेसर-मिकाली क्रिप्टोप्रणाली (द्विघात पुनर्वितरण समस्या)
-अवशिष्टता समस्याओं की कठोरता पर भरोसा करने वाले कुछ क्रिप्टो सिस्टम में शामिल हैं:
+* [[ब्लम ब्लम डंप जनरेटर|ब्लम ब्लम शुब जनरेटर]] (द्विघात पुनर्वितरण समस्या)
-*Goldwasser–Micali क्रिप्टोसिस्टम (द्विघात पुनर्वितरण समस्या)
+*[[पैलियर क्रिप्टोसिस्टम|पैलियर क्रिप्टोप्रणाली]] (निर्णायक संयुक्त अवशिष्टता समस्या)
-* [[ब्लम ब्लम डंप जनरेटर]] (द्विघात पुनर्वितरण समस्या)
+*[[ बेनलोह क्रिप्टोसिस्टम |बेनालोह क्रिप्टोप्रणाली]] (उच्च अवशिष्टता समस्या)
-*[[पैलियर क्रिप्टोसिस्टम]] (निर्णायक समग्र अवशिष्टता समस्या)
+*नाकाचे-स्टर्न क्रिप्टोप्रणाली (उच्च अवशिष्टता समस्या)
-*[[ बेनलोह क्रिप्टोसिस्टम ]] (उच्च अवशिष्टता समस्या)
-*नाकाचे-स्टर्न क्रिप्टोसिस्टम (उच्च अवशिष्टता समस्या)
 ==== फी-छिपी धारणा ====
-{{Main|Phi-hiding assumption}}
+{{Main|फी-छुपी धारणा}}
-एक समग्र संख्या के लिए <math>m</math>, यह ज्ञात नहीं है कि अपने यूलर के कुल कार्य की कुशलता से गणना कैसे करें <math>\phi(m)</math>. फी-हाइडिंग धारणा यह मानती है कि गणना करना कठिन है <math>\phi(m)</math>, और इसके अलावा किसी भी प्रमुख कारकों की गणना करना <math>\phi(m)</math> कठिन है। इस धारणा का उपयोग काचिन-मिकाली-स्टैडलर [[निजी सूचना पुनर्प्राप्ति]] प्रोटोकॉल में किया जाता है।<ref>{{cite journal |last1=Cachin |first1=Christian |last2=Micali |first2=Silvio|last3=Stadler|first3=Markus|year=1999|title=बहुलघुगणक संचार के साथ कम्प्यूटेशनल रूप से निजी सूचना पुनर्प्राप्ति|publisher=Springer|volume= 1592|pages=402–414|journal=Lecture Notes in Computer Science|doi=10.1007/3-540-48910-X |editor1-last=Stern |editor1-first=Jacques|isbn=978-3-540-65889-4 |s2cid=29690672 }}</ref>
+संयुक्त संख्या <math>m</math> के लिए, यह ज्ञात नहीं है कि अपने यूलर के कुल फलन <math>\phi(m)</math> की कुशलतापूर्वक गणना कैसे की जाए। फी-हाइडिंग की धारणा यह मानती है कि <math>\phi(m)</math> की गणना करना कठिन है, और इसके अतिरिक्त <math>\phi(m)</math> के किसी भी प्रमुख कारकों की गणना करना कठिन है। इस धारणा का उपयोग काचिन-मिकाली-स्टैडलर [[निजी सूचना पुनर्प्राप्ति|पीआईआर]] प्रोटोकॉल में किया जाता है।<ref>{{cite journal |last1=Cachin |first1=Christian |last2=Micali |first2=Silvio|last3=Stadler|first3=Markus|year=1999|title=बहुलघुगणक संचार के साथ कम्प्यूटेशनल रूप से निजी सूचना पुनर्प्राप्ति|publisher=Springer|volume= 1592|pages=402–414|journal=Lecture Notes in Computer Science|doi=10.1007/3-540-48910-X |editor1-last=Stern |editor1-first=Jacques|isbn=978-3-540-65889-4 |s2cid=29690672 }}</ref>
 === असतत लॉग समस्या (डीएलपी) ===
-{{Main|Discrete logarithm}}
+{{Main|असतत लघुगणक}}
-दिए गए तत्व <math>a</math> और <math>b</math> एक समूह से (गणित) <math>G</math>असतत लॉग समस्या एक पूर्णांक के लिए पूछती है <math>k</math> ऐसा है कि <math>a=b^k</math>.
+समूह <math>G</math> से दिए गए तत्व <math>a</math> और <math>b</math>, असतत लॉग समस्या पूर्णांक <math>k</math> के लिए पूछती है जैसे कि <math>a=b^k</math>। असतत लॉग समस्या को पूर्णांक गुणनखंडन के साथ तुलना करने के लिए नहीं जाना जाता है, लेकिन उनकी कम्प्यूटेशनल जटिलताएं निकट से संबंधित हैं।
-असतत लॉग समस्या को पूर्णांक फ़ैक्टराइज़ेशन के साथ तुलना करने के लिए नहीं जाना जाता है, लेकिन उनकी कम्प्यूटेशनल जटिलता असतत लघुगणक # पूर्णांक फ़ैक्टराइज़ेशन के साथ तुलना है।
-असतत लॉग समस्या से संबंधित अधिकांश क्रिप्टोग्राफिक प्रोटोकॉल वास्तव में मजबूत कम्प्यूटेशनल डिफी-हेलमैन धारणा | डिफी-हेलमैन धारणा: दिए गए समूह तत्वों पर भरोसा करते हैं <math>g, g^a, g^b</math>, कहाँ <math>g</math> एक जनरेटर है और <math>a,b</math> यादृच्छिक पूर्णांक हैं, इसे खोजना कठिन है <math>g^{a\cdot b}</math>. इस धारणा का उपयोग करने वाले प्रोटोकॉल के उदाहरणों में मूल डिफी-हेलमैन कुंजी विनिमय, साथ ही साथ [[ElGamal एन्क्रिप्शन]] शामिल है (जो अभी तक मजबूत निर्णायक डिफी-हेलमैन धारणा पर निर्भर करता है। निर्णायक डिफी-हेलमैन (डीडीएच) संस्करण)।
+असतत लॉग समस्या से संबंधित अधिकांश क्रिप्टोग्राफिक प्रोटोकॉल वास्तव में कठोर कम्प्यूटेशनल डिफी-हेलमैन धारणा पर विश्वास करते हैं: दिए गए समूह तत्वों <math>g, g^a, g^b</math>, जहाँ <math>g</math> जनरेटर है और <math>a,b</math> यादृच्छिक पूर्णांक हैं, इससे <math>g^{a\cdot b}</math> ढूँढना कठिन है। इस धारणा का उपयोग करने वाले प्रोटोकॉल के उदाहरणों में मूल डिफी-हेलमैन कुंजी विनिमय, साथ ही साथ [[ElGamal एन्क्रिप्शन|एलगामल एन्क्रिप्शन]] (जो अभी तक कठोर निर्णायक डिफी-हेलमैन (डीडीएच) संस्करण पर निर्भर करता है) सम्मिलित हैं।
 ==== बहुरेखीय मानचित्र ====
-एक [[बहुरेखीय नक्शा]] एक कार्य है <math>e: G_1 ,\dots,G_n \rightarrow G_T</math> (कहाँ <math>G_1 ,\dots,G_n,G_T</math> समूह (गणित)) ऐसे हैं कि किसी के लिए भी <math>g_1, \dots, g_n \in G_1, \dots G_n</math> और <math>a_1, \dots, a_n</math>,
+[[बहुरेखीय नक्शा|बहुरेखीय मानचित्र]] फलन <math>e: G_1 ,\dots,G_n \rightarrow G_T</math> है, (जहाँ <math>G_1 ,\dots,G_n,G_T</math> समूह) ऐसे हैं कि हर किसी के लिए <math>g_1, \dots, g_n \in G_1, \dots G_n</math> और <math>a_1, \dots, a_n</math> :
-:<math>e(g_1^{a_1},\dots,g_n^{a_n}) = e(g_1,\dots,g_n)^{a_1\cdots a_n}</math>.
+:<math>e(g_1^{a_1},\dots,g_n^{a_n}) = e(g_1,\dots,g_n)^{a_1\cdots a_n}</math>
-क्रिप्टोग्राफ़िक अनुप्रयोगों के लिए, कोई समूह बनाना चाहेगा <math>G_1 ,\dots,G_n,G_T</math> और एक नक्शा <math>e</math> ऐसे में मैप और ग्रुप का संचालन चालू रहता है <math>G_1 ,\dots,G_n,G_T</math> कुशलता से गणना की जा सकती है, लेकिन असतत लॉग समस्या चालू है <math>G_1 ,\dots,G_n</math> अभी भी कठिन है।<ref name = BS02>
+क्रिप्टोग्राफ़िक अनुप्रयोगों के लिए, कोई समूह <math>G_1 ,\dots,G_n,G_T</math> और मानचित्र <math>e</math> का निर्माण करना चाहेगा, जैसे कि मानचित्र और <math>G_1 ,\dots,G_n,G_T</math> पर समूह संचालन को कुशलता से गणना की जा सकती है, लेकिन <math>G_1 ,\dots,G_n</math> पर असतत लॉग समस्या अभी भी कठिन है। कुछ अनुप्रयोगों के लिए मजबूत धारणाओं की आवश्यकता होती है, उदाहरण; डिफी-हेलमैन धारणाओं के बहुरेखीय अनुरूप।<ref name = BS02>
 {{cite journal |author1-link= Dan Boneh|first1=Dan|last1=Boneh|author2-link=Alice Silverberg|first2=Alice|last2=Silverberg|year= 2002|title= Applications of Multilinear Forms to Cryptography|url= https://eprint.iacr.org/2002/080|journal= Cryptology ePrint Archive}}</ref>
-कुछ अनुप्रयोगों के लिए मजबूत धारणाओं की आवश्यकता होती है, उदा। डिफी-हेलमैन मान्यताओं के बहुरेखीय अनुरूप।
-के विशेष मामले के लिए <math>n=2</math>[[वील पेयरिंग]] और [[ टेट बाँधना ]] का उपयोग करके विश्वसनीय सुरक्षा के साथ [[बिलिनियर मैपिंग]] का निर्माण किया गया है।<ref name = DBS04>
+<math>n=2</math> की विशेष स्थिति के लिए, [[वील पेयरिंग]] और [[टेट बाँधना|टेट पेयरिंग]] का उपयोग करके विश्वसनीय सुरक्षा के साथ [[बिलिनियर मैपिंग|द्विरेखीय मानचित्रों]] का निर्माण किया गया है।<ref name="DBS04">
-{{cite journal |first1= Ratna|last1=Dutta|first2= Rana|last2=Barua|first3 = Palash|last3=Sarkar|year= 2004|title= Pairing-Based Cryptographic Protocols : A Survey|url= https://eprint.iacr.org/2004/064|journal= Cryptology ePrint Archive}}</ref>
+{{cite journal |first1= Ratna|last1=Dutta|first2= Rana|last2=Barua|first3 = Palash|last3=Sarkar|year= 2004|title= Pairing-Based Cryptographic Protocols : A Survey|url= https://eprint.iacr.org/2004/064|journal= Cryptology ePrint Archive}}</ref> <math>n>2</math> के लिए हाल के वर्षों में कई निर्माण प्रस्तावित किए गए हैं, लेकिन उनमें से कई टूट भी गए हैं, और वर्तमान में सुरक्षित प्रत्याशी के बारे में कोई सहमति नहीं है।<ref>
-के लिए <math>n>2</math> हाल के वर्षों में कई निर्माण प्रस्तावित किए गए हैं, लेकिन उनमें से कई टूट भी गए हैं, और वर्तमान में एक सुरक्षित उम्मीदवार के बारे में कोई सहमति नहीं है।<ref>
 {{cite web |url= http://malb.io/are-graded-encoding-schemes-broken-yet.html|title= Are Graded Encoding Scheme broken yet?|first= Martin R.|last=Albrecht|access-date= 22 March 2018}}</ref>
-बहुरेखीय कठोरता मान्यताओं पर भरोसा करने वाले कुछ क्रिप्टो सिस्टम में शामिल हैं:
-* [[बोन-फ्रैंकलिन योजना]] (ब्लिनियर डिफी-हेलमैन)
+बहुरेखीय कठोरता धारणाओं पर विश्वास करने वाले कुछ क्रिप्टो प्रणाली में सम्मिलित हैं:
+* [[बोन-फ्रैंकलिन योजना|बोनेह-फ्रैंकलिन योजना]] (ब्लिनियर डिफी-हेलमैन)
 * बोनेह-लिन-शचम (ब्लिनियर डिफी-हेलमैन)
-* गर्ग-जेंट्री-हलेवी-रायकोवा-सहाय-वाटर्स अप्रभेद्यता अस्पष्टता और [[कार्यात्मक एन्क्रिप्शन]] के लिए उम्मीदवार (बहुरेखीय पहेली)<ref>
+* गर्ग-जेंट्री-हलेवी-रायकोवा-सहाय-वाटर्स अप्रभेद्यता अस्पष्टता और [[कार्यात्मक एन्क्रिप्शन]] के लिए प्रत्याशी (बहुरेखीय पहेली)<ref>
 {{cite journal |first1 = Sanjam|last1=Garg| first2 = Craig|last2=Gentry| first3 = Shai|last3=Halevi| first4 = Mariana |last4=Raykova| first5 = Amit|last5=Sahai|first6 = Brent |last6=Waters|year=2016|title=Candidate Indistinguishability Obfuscation and Functional Encryption for All Circuits|publisher=SIAM|volume= 45|number=3|pages=882–929|url=https://eprint.iacr.org/2013/451.pdf|journal=[[SIAM Journal on Computing]]|doi=10.1137/14095772X}}</ref>
-=== जाली की समस्या ===
+=== लैटिस की समस्या ===
-{{Main|Lattice problem}}
+{{Main|लैटिस समस्या}}
-जाली पर सबसे मौलिक कम्प्यूटेशनल समस्या है जाली समस्या # सबसे छोटी वेक्टर समस्या (एसवीपी) | सबसे छोटी वेक्टर समस्या (एसवीपी): एक जाली दी गई <math>L</math>, सबसे छोटा गैर-शून्य वेक्टर खोजें <math>v \in L</math>.
-अधिकांश क्रिप्टोसिस्टम्स को एसवीपी के रूपों पर मजबूत धारणाओं की आवश्यकता होती है, जैसे लैटिस समस्या # सबसे छोटी स्वतंत्र वैक्टर समस्या (एसआईवीपी) | सबसे छोटी स्वतंत्र वैक्टर समस्या (एसआईवीपी), जाली समस्या # गैपएसवीपी,<ref name = peikert09>{{cite conference
+लैटिस पर सबसे मौलिक कम्प्यूटेशनल समस्या है, सबसे छोटी सदिश समस्या (एसवीपी) है: लैटिस <math>L</math> दी गई, <math>v \in L</math> में सबसे लघु गैर-शून्य सदिश खोजें। अधिकांश क्रिप्टोप्रणाली को एसवीपी के रूपों पर कठोर धारणाओं की आवश्यकता होती है, जैसे कि लघुतम स्वतंत्र सदिश समस्या (एसआईवीपी), गैपएसवीपी,<ref name="peikert09">{{cite conference
   | first = Chris |last=Peikert
   | contribution = Public-key cryptosystems from the worst-case shortest vector problem: extended abstract
@@ Line 113: / Line 100: @@
   | pages = 333–342
   | title = Proceedings on 41st Annual ACM Symposium on Theory of Computing (STOC)
-  | year = 2009}}</ref> या यूनीक-एसवीपी।<ref name = ad97>{{cite conference
+  | year = 2009}}</ref> या अद्वितीय-एसवीपी।<ref name = ad97>{{cite conference
   | author1-link = Miklós Ajtai | first1=Miklós|last1= Ajtai
   | author2-link = Cynthia Dwork|first2=Cynthia|last2=Dwork
@@ Line 122: / Line 109: @@
   | year = 1997}}
 </ref>
-क्रिप्टोग्राफी में सबसे उपयोगी जाली कठोरता धारणा सीखने के साथ त्रुटियों (एलडब्ल्यूई) समस्या के लिए है: दिए गए नमूने <math>(x,y)</math>, कहाँ <math>y=f(x)</math> कुछ रैखिक कार्यों के लिए <math>f(\cdot)</math>, सीखना आसान है <math>f(\cdot)</math> रैखिक बीजगणित का उपयोग करना। एलडब्ल्यूई समस्या में, एल्गोरिथम के इनपुट में त्रुटियाँ हैं, अर्थात प्रत्येक जोड़ी के लिए <math>y\neq f(x)</math> कुछ छोटी संभावना के साथ। माना जाता है कि त्रुटियां समस्या को दुरूह बनाती हैं (उचित मापदंडों के लिए); विशेष रूप से, एसवीपी के वेरिएंट से सबसे खराब स्थिति से लेकर औसत स्थिति तक की कमी ज्ञात है।<ref name = regev10>{{cite conference
+क्रिप्टोग्राफी में सबसे उपयोगी लैटिस कठोरता धारणा सीखने के साथ त्रुटियों (एलडब्ल्यूई) समस्या के लिए है: दिए गए नमूने <math>(x,y)</math>, जहाँ <math>y=f(x)</math> कुछ रैखिक फलन <math>f(\cdot)</math> के लिए, <math>f(\cdot)</math> रैखिक बीजगणित का उपयोग करके यह सीखना सरल है। एलडब्ल्यूई समस्या में, एल्गोरिथम के इनपुट में त्रुटियाँ हैं, अर्थात प्रत्येक जोड़ी के लिए <math>y\neq f(x)</math> कुछ छोटी संभावना के साथ है। माना जाता है कि त्रुटियां समस्या को असभ्य बनाती हैं (उचित मापदंडों के लिए); विशेष रूप से, एसवीपी के वेरिएंट से सबसे खराब स्थिति से लेकर औसत स्थिति तक की कमी ज्ञात करती है।<ref name="regev10">{{cite conference
   | first = Oded |last=Regev
   | contribution = The Learning with Errors Problem (Invited Survey)
@@ Line 130: / Line 118: @@
   | year = 2010|title-link=Computational Complexity Conference
   }}</ref>
-क्वांटम कंप्यूटरों के लिए, फैक्टरिंग और असतत लॉग समस्याएं आसान हैं, लेकिन जाली की समस्याओं को कठिन माना जाता है।<ref name = peikert16>{{cite journal |first = Chris|last= Peikert|year= 2016|title= जाली क्रिप्टोग्राफी का एक दशक|url= https://eprint.iacr.org/2015/939|journal= Foundations and Trends in Theoretical Computer Science|volume= 10|number = 4|pages = 283–424|doi= 10.1561/0400000074}}</ref>
-यह कुछ [[जाली आधारित क्रिप्टोग्राफी]] बनाता है | लैटिस-आधारित क्रिप्टोसिस्टम [[पोस्ट-क्वांटम क्रिप्टोग्राफी]] के लिए उम्मीदवार हैं।
-जाली समस्याओं की कठोरता पर भरोसा करने वाले कुछ क्रिप्टो सिस्टम में शामिल हैं:
+क्वांटम कंप्यूटरों के लिए, फैक्टरिंग और असतत लॉग समस्याएं सरल हैं, लेकिन लैटिस की समस्याओं को कठिन माना जाता है।<ref name="peikert16">{{cite journal |first = Chris|last= Peikert|year= 2016|title= जाली क्रिप्टोग्राफी का एक दशक|url= https://eprint.iacr.org/2015/939|journal= Foundations and Trends in Theoretical Computer Science|volume= 10|number = 4|pages = 283–424|doi= 10.1561/0400000074}}</ref> यह कुछ [[जाली आधारित क्रिप्टोग्राफी|लैटिस आधारित क्रिप्टोग्राफी]] को [[पोस्ट-क्वांटम क्रिप्टोग्राफी]] के लिए उपयुक्त बनाता है।
-*[[NTRU]] ([[NTRUEncrypt]] और [[NTRUSign]] दोनों)
-* [[होमोमोर्फिक एन्क्रिप्शन]] के लिए अधिकांश उम्मीदवार
+लैटिस समस्याओं की कठोरता पर विश्वास करने वाले कुछ क्रिप्टो प्रणाली में सम्मिलित हैं:
+*[[NTRU|एनटीआरयू]] ([[NTRUEncrypt|एनटीआरयूएन्क्रिप्ट]] और [[NTRUSign|एनटीआरयूसाइन]] दोनों)
+* पूरी तरह से [[होमोमोर्फिक एन्क्रिप्शन]] के लिए अधिकांश प्रत्याशी
 == गैर-क्रिप्टोग्राफ़िक कठोरता धारणाएँ ==
-साथ ही उनके क्रिप्टोग्राफ़िक अनुप्रयोगों के साथ-साथ कठोरता मान्यताओं का उपयोग कम्प्यूटेशनल जटिलता सिद्धांत में गणितीय बयानों के सबूत प्रदान करने के लिए किया जाता है जो बिना शर्त साबित करना मुश्किल होता है। इन अनुप्रयोगों में, कोई यह साबित करता है कि कठोरता धारणा कुछ वांछित जटिलता-सैद्धांतिक कथन का अर्थ है, यह साबित करने के बजाय कि कथन स्वयं सत्य है। इस प्रकार की सबसे प्रसिद्ध धारणा यह है कि पी बनाम एनपी समस्या|पी ≠ एनपी,<ref>{{cite journal|first=Lance|last=Fortnow|author-link=Lance Fortnow|url=http://www.cs.uchicago.edu/~fortnow/papers/pnp-cacm.pdf|archive-url=https://wayback.archive-it.org/all/20110224135332/http://www.cs.uchicago.edu/~fortnow/papers/pnp-cacm.pdf|url-status=dead|archive-date=2011-02-24|title=पी बनाम एनपी समस्या की स्थिति|journal=[[Communications of the ACM]]|volume=52|year=2009|issue=9|pages=78–86|doi=10.1145/1562164.1562186|s2cid=5969255}}.</ref> लेकिन अन्य में [[घातीय समय परिकल्पना]] शामिल है,<ref>{{cite book
+साथ ही उनके क्रिप्टोग्राफ़िक अनुप्रयोगों के साथ-साथ कठोरता धारणाओं का उपयोग कम्प्यूटेशनल जटिलता सिद्धांत में गणितीय उल्लेखों के प्रमाण प्रदान करने के लिए किया जाता है, जो बिना नियमों के प्रमाणित करना जटिल होता है। इन अनुप्रयोगों में, कोई यह प्रमाणित करता है कि कठोरता धारणा कुछ वांछित जटिलता-सैद्धांतिक कथन का अर्थ है, यह प्रमाणित करने के अतिरिक्त कि कथन स्वयं सत्य है। इस प्रकार की सबसे प्रसिद्ध धारणा यह है कि '''P ≠ NP''', <ref>{{cite journal|first=Lance|last=Fortnow|author-link=Lance Fortnow|url=http://www.cs.uchicago.edu/~fortnow/papers/pnp-cacm.pdf|archive-url=https://wayback.archive-it.org/all/20110224135332/http://www.cs.uchicago.edu/~fortnow/papers/pnp-cacm.pdf|url-status=dead|archive-date=2011-02-24|title=पी बनाम एनपी समस्या की स्थिति|journal=[[Communications of the ACM]]|volume=52|year=2009|issue=9|pages=78–86|doi=10.1145/1562164.1562186|s2cid=5969255}}.</ref> लेकिन अन्य में [[घातीय समय परिकल्पना]], प्लांटेड क्लिक धारणा, और [[अद्वितीय खेल अनुमान|अद्वितीय खेल धारणा]] सम्मिलित है।<ref>{{cite book
   | last = Woeginger | first = Gerhard | author-link = Gerhard J. Woeginger
   | doi = 10.1007/3-540-36478-1_17
@@ Line 146: / Line 134: @@
   | contribution = Exact algorithms for NP-hard problems: A survey
   | year = 2003
-  | volume = 2570}}.</ref> प्लांटेड गुट, और [[अद्वितीय खेल अनुमान]]।<ref name = khot10>{{cite conference
+  | volume = 2570}}.</ref><ref name = khot10>{{cite conference
   | author-link = Subhash Khot
   | last = Khot | first = Subhash
@@ Line 158: / Line 146: @@
-=== सी-हार्ड समस्याएं ===
+=== सी-कठोर समस्याएं ===
-कई वर्स्ट-केस जटिलता|वर्स्ट-केस कम्प्यूटेशनल समस्याओं को कुछ [[जटिलता वर्ग]] के लिए कठिन या [[पूर्ण (जटिलता)]] के रूप में जाना जाता है <math>C</math>, विशेष रूप से [[ एनपी-कठोरता ]]|एनपी-हार्ड (लेकिन अक्सर [[पीएसपीएसीई-पूर्ण समस्याओं की सूची]]|पीएसपीएसीई-हार्ड, [[पीपीएडी-पूर्ण समस्याओं की सूची]]|पीपीएडी-हार्ड, आदि)। इसका मतलब यह है कि वे कम से कम उतने ही कठिन हैं जितनी कि कक्षा की कोई समस्या <math>C</math>.
+कई सबसे खराब-स्थिति वाली कम्प्यूटेशनल समस्याओं को कुछ [[जटिलता वर्ग]] <math>C</math> के लिए कठिन या [[पूर्ण (जटिलता)|पूर्ण]] होने के लिए जाना जाता है, विशेष रूप से [[ एनपी-कठोरता |एनपी-कठोरता]] (लेकिन अधिकांशतः [[पीएसपीएसीई-पूर्ण समस्याओं की सूची|पीएसपीएसीई-कठोर]], [[पीपीएडी-पूर्ण समस्याओं की सूची|पीपीएडी-कठोर]] आदि)। इसका अर्थ यह है कि वे वर्ग <math>C</math> में किसी भी समस्या के रूप में कम से कम कठिन हैं। यदि कोई समस्या <math>C</math>-कठोर है (बहुपद समय में कमी के संबंध में), तो इसे बहुपद-समय एल्गोरिदम द्वारा हल नहीं किया जा सकता है जब तक कि कम्प्यूटेशनल कठोरता धारणा <math>P \neq C</math> असत्य है।
-यदि कोई समस्या है <math>C</math>-हार्ड (बहुपद समय में कमी के संबंध में), तो इसे बहुपद-समय एल्गोरिदम द्वारा हल नहीं किया जा सकता जब तक कि कम्प्यूटेशनल कठोरता धारणा नहीं <math>P \neq C</math> गलत है।
 === घातीय समय परिकल्पना (ईटीएच) और वेरिएंट्स ===
-{{Main|Exponential time hypothesis}}
+{{Main|घातीय समय परिकल्पना}}
-घातीय समय परिकल्पना (ETH) की कठोरता मान्यताओं की #शक्ति है <math>P \neq NP</math> कठोरता धारणा, जो अनुमान लगाती है कि न केवल [[बूलियन संतुष्टि समस्या]] में बहुपद समय एल्गोरिथ्म नहीं है, बल्कि इसके लिए घातीय समय की आवश्यकता है (<math>2^{\Omega(n)}</math>).<ref>{{cite conference
+घातीय समय परिकल्पना (ईटीएच) <math>P \neq NP</math> की कठोरता धारणाओं का सुदृढ़ीकरण है, जो अनुमान लगता है कि न केवल [[बूलियन संतुष्टि समस्या]] में बहुपद समय एल्गोरिथ्म नहीं है, बल्कि इसके लिए घातीय समय (<math>2^{\Omega(n)}</math>) की भी आवश्यकता नही है।<ref>{{cite conference
   | last1 = Impagliazzo | first1 = Russell | author1-link = Russell Impagliazzo
   | last2 = Paturi | first2 = Ramamohan
@@ Line 171: / Line 159: @@
   | pages = 237–240
   | title = Proc. 14th IEEE Conf. on Computational Complexity
-  | year = 1999}}</ref> एक और भी मजबूत धारणा, जिसे एक्सपोनेंशियल टाइम परिकल्पना (SETH) के रूप में जाना जाता है, यह अनुमान लगाती है कि बूलियन संतुष्टि समस्या |<math>k</math>-सैट की आवश्यकता है <math>2^{(1-\varepsilon_k)n}</math> समय, कहाँ <math>\lim_{k \rightarrow \infty} \varepsilon_k = 0</math>.
+  | year = 1999}}</ref> एक और भी कठोर धारणा, जिसे एक्सपोनेंशियल टाइम परिकल्पना (एसईटीएच) के रूप में जाना जाता है, यह अनुमान लगाती है कि <math>k</math>-सैट को <math>2^{(1-\varepsilon_k)n}</math>समय की आवश्यकता होती है, जहाँ <math>\lim_{k \rightarrow \infty} \varepsilon_k = 0</math> है। ईटीएच, एसईटीएच, और संबंधित कम्प्यूटेशनल कठोरता धारणाएं सूक्ष्म जटिलता परिणामों को कम करने की अनुमति देती हैं, उदाहरण; परिणाम जो बहुपद समय और अर्ध-बहुपद समय में अंतर करते हैं,<ref name=BKW15 /> या यहाँ तक कि <math>n^{1.99}</math> और <math>n^2</math> [[पैरामीट्रिज्ड जटिलता]] में ऐसी धारणाएं भी उपयोगी होती हैं।<ref>{{cite conference
-ईटीएच, एसईटीएच, और संबंधित कम्प्यूटेशनल कठोरता धारणाएं सूक्ष्म जटिलता परिणामों को कम करने की अनुमति देती हैं, उदा। परिणाम जो बहुपद समय और समय जटिलता को अलग करते हैं#अर्ध-बहुपद समय|अर्ध-बहुपद समय,<ref name=BKW15 />या और भी <math>n^{1.99}</math> बनाम <math>n^2</math>.<ref>{{cite conference
   | last1 = Abboud | first1 = Amir
   | last2 = Vassilevska-Williams | first2 = Virginia |author2-link = Virginia Vassilevska Williams
@@ Line 180: / Line 167: @@
   | pages = 39–51
   | title = Automata, Languages, and Programming - 41st International Colloquium, ICALP 2014
-  | year = 2014}}</ref>
+  | year = 2014}}</ref><ref name = LMS11>
-[[पैरामीट्रिज्ड जटिलता]] में ऐसी धारणाएं भी उपयोगी होती हैं।<ref name = LMS11>
 {{cite journal
   | last1 = Lokshtanov | first1 = Daniel
@@ Line 195: / Line 181: @@
-=== औसत-मामला कठोरता धारणा ===
+=== औसत-स्थिति कठोरता धारणा ===
-{{Main|Average-case complexity}}
+{{Main|औसत-स्थिति की जटिलता}}
-कुछ कम्प्यूटेशनल समस्याओं को उदाहरणों के एक विशेष वितरण पर औसतन कठिन माना जाता है।
+कुछ कम्प्यूटेशनल समस्याओं को उदाहरणों के विशेष वितरण पर औसतन कठिन माना जाता है। उदाहरण के लिए, प्लांटेड क्लिक समस्या में, इनपुट यादृच्छिक ग्राफ नमूना है, एर्डोस-रेनी रैंडम ग्राफ का नमूना लेकर और फिर यादृच्छिक <math>k</math>-क्लिक "रोपण", अर्थात् <math>k</math> के समान रूप से यादृच्छिक नोड्स को जोड़ना (जहाँ <math>2\log_2 n \ll k \ll \sqrt n</math>) और लक्ष्य प्लांटेड <math>k</math>- क्लिक (जो अद्वितीय डब्ल्यू.एच.पी. है) को खोजना है।<ref name="ab">{{cite book|title=Computational Complexity: A Modern Approach|first1=Sanjeev|last1=Arora|author1-link=Sanjeev Arora|first2=Boaz|last2=Barak|publisher=Cambridge University Press|year=2009|isbn=9780521424264|pages=362–363|url=https://books.google.com/books?id=8Wjqvsoo48MC&pg=PA362}}.</ref> अन्य महत्वपूर्ण उदाहरण फीगे की परिकल्पना है, जो 3-एसएटी के यादृच्छिक उदाहरणों के बारे में कम्प्यूटेशनल कठोरता धारणा है (चरों के खंड के विशिष्ट अनुपात को बनाए रखने के लिए नमूना)।<ref name = Feige02>
-उदाहरण के लिए, प्लांटेड क्लिक समस्या में, इनपुट एक यादृच्छिक ग्राफ नमूना है, एक एर्दोस-रेनी मॉडल का नमूना लेकर | एर्डोस-रेनी यादृच्छिक ग्राफ और फिर एक यादृच्छिक रोपण <math>k</math>-क्लिक, यानी कनेक्ट करना <math>k</math> समान रूप से यादृच्छिक नोड्स (जहाँ <math>2\log_2 n \ll k \ll \sqrt n</math>), और लक्ष्य लगाए गए को ढूंढना है <math>k</math>-क्लिक (जो अद्वितीय w.h.p. है)।<ref name="ab">{{cite book|title=Computational Complexity: A Modern Approach|first1=Sanjeev|last1=Arora|author1-link=Sanjeev Arora|first2=Boaz|last2=Barak|publisher=Cambridge University Press|year=2009|isbn=9780521424264|pages=362–363|url=https://books.google.com/books?id=8Wjqvsoo48MC&pg=PA362}}.</ref>
-एक अन्य महत्वपूर्ण उदाहरण उरीएल फीगे की परिकल्पना है, जो बूलियन संतुष्टि समस्या के यादृच्छिक उदाहरणों के बारे में एक कम्प्यूटेशनल कठोरता धारणा है | 3-एसएटी (चर के खंड के विशिष्ट अनुपात को बनाए रखने के लिए नमूना)।<ref name = Feige02>
 {{cite conference
 | last1 = Feige | first1 = Uriel |author1-link = Uriel Feige
@@ Line 207: / Line 191: @@
   | title = Proceedings on 34th Annual ACM Symposium on Theory of Computing (STOC)
   | year = 2002
-}}</ref>
+}}</ref> औसत-स्थिति कम्प्यूटेशनल कठोरता धारणाएँ आँकड़ों जैसे अनुप्रयोगों में औसत-स्थिति कठोरता को प्रमाणित करने के लिए उपयोगी होती हैं, जहाँ इनपुट पर प्राकृतिक वितरण होता है।<ref name = BR13>
-औसत-केस कम्प्यूटेशनल कठोरता धारणाएँ आँकड़ों जैसे अनुप्रयोगों में औसत-केस कठोरता को साबित करने के लिए उपयोगी होती हैं, जहाँ इनपुट पर प्राकृतिक वितरण होता है।<ref name = BR13>
 {{cite conference
 | last1 = Berthet | first1 = Quentin
@@ Line 217: / Line 200: @@
   | url = http://jmlr.org/proceedings/papers/v30/Berthet13.html
   | year = 2013
-}}</ref>
+}}</ref> इसके अतिरिक्त, प्लांटेड क्लिक कठोरता धारणा का उपयोग अन्य समस्याओं के बहुपद और अर्ध-बहुपद सबसे खराब समय जटिलता के बीच अंतर करने के लिए भी किया गया है,<ref name = HK11>{{cite journal
-इसके अतिरिक्त, प्लांटेड क्लिक हार्डनेस धारणा का उपयोग अन्य समस्याओं के बहुपद और अर्ध-बहुपद वर्स्ट-केस टाइम जटिलता के बीच अंतर करने के लिए भी किया गया है,<ref name = HK11>{{cite journal
   | last1 = Hazan | first1 = Elad
   | last2 = Krauthgamer | first2 = Robert
@@ Line 228: / Line 210: @@
   | number = 1
   | year = 2011| citeseerx = 10.1.1.139.7326
-  }}</ref>
+  }}</ref> इसी तरह घातीय समय परिकल्पना के लिए भी किया गया है।
-इसी तरह #Exponential Time Hypothesis (ETH) और वेरिएंट।
+=== अद्वितीय खेल ===
+{{Main|अद्वितीय खेल अनुमान}}
-=== अनोखा खेल ===
+अद्वितीय लेबल कवर समस्या, बाधा संतुष्टि समस्या है, जहां प्रत्येक बाधा <math>C</math> में दो चर <math>x,y</math> सम्मिलित हैं, और <math>x</math> के प्रत्येक मान के लिए <math>y</math> अद्वितीय मान है जो <math>C</math> को संतुष्ट करता है। यह निर्धारित करना कि क्या सभी बाधाओं को पूरा किया जा सकता है, आसान है, लेकिन अद्वितीय खेल कंजेक्चर (यूजीसी) का मानना है कि यह निर्धारित करना कि क्या लगभग सभी बाधाएं (<math>(1-\varepsilon)</math>-अंश, किसी भी स्थिरांक के लिए <math>\varepsilon>0</math>) संतुष्ट हो सकते हैं या उनमें से कोई नहीं (<math>\varepsilon</math>-अंश) भी संतुष्ट किया जा सकता है, वे एनपी-कठोर है।<ref name=khot10 /> सन्निकटन समस्याओं को अक्सर यूजीसी मानते हुए एनपी-कठोर के रूप में जाना जाता है; ऐसी समस्याओं को यूजी-कठोर कहा जाता है। विशेष रूप से, यह मानते हुए कि यूजीसी में अर्ध-निश्चित प्रोग्रामिंग एल्गोरिथम है जो कई महत्वपूर्ण समस्याओं के लिए इष्टतम सन्निकटन गारंटी प्राप्त करता है।<ref name = rag08>
-{{Main|Unique games conjecture}}
-अनोखा खेल अनुमान #अद्वितीय लेबल कवर समस्या एक बाधा संतुष्टि समस्या है, जहां प्रत्येक बाधा <math>C</math> दो चर शामिल हैं <math>x,y</math>, और के प्रत्येक मूल्य के लिए <math>x</math> का एक अनूठा मूल्य है <math>y</math> जो संतुष्ट करता है <math>C</math>.
-यह निर्धारित करना कि क्या सभी बाधाओं को पूरा किया जा सकता है, आसान है, लेकिन यूनीक गेम कंजेक्चर (यूजीसी) का मानना है कि यह निर्धारित करना कि क्या लगभग सभी बाधाएं (<math>(1-\varepsilon)</math>-अंश, किसी भी स्थिरांक के लिए <math>\varepsilon>0</math>) संतुष्ट हो सकते हैं या उनमें से लगभग कोई नहीं (<math>\varepsilon</math>-अंश) संतुष्ट किया जा सकता है एनपी-हार्ड है।<ref name=khot10 />सन्निकटन समस्याओं को अक्सर यूजीसी मानते हुए एनपी-हार्ड के रूप में जाना जाता है; ऐसी समस्याओं को यूजी-हार्ड कहा जाता है।
-विशेष रूप से, यह मानते हुए कि UGC में एक अर्ध-निश्चित प्रोग्रामिंग एल्गोरिथम है जो कई महत्वपूर्ण समस्याओं के लिए इष्टतम सन्निकटन गारंटी प्राप्त करता है।<ref name = rag08>
 {{cite conference
   | first = Prasad |last=Raghavendra
@@ Line 245: / Line 225: @@
-====छोटा सेट विस्तार====
+====लघु सेट विस्तार====
-{{main|Small set expansion hypothesis}}
+{{main|लघु सेट विस्तार परिकल्पना}}
-यूनिक लेबल कवर समस्या से निकटता से संबंधित है स्मॉल सेट एक्सपेंशन (SSE) समस्या: एक ग्राफ दिया गया <math>G = (V,E)</math>, वर्टिकल का एक छोटा सेट खोजें (आकार का <math>n/\log(n)</math>) जिसका विस्तारक ग्राफ#एज विस्तार न्यूनतम है।
-यह ज्ञात है कि यदि SSE का अनुमान लगाना कठिन है, तो अद्वितीय लेबल कवर भी ऐसा ही है। इसलिए, स्मॉल सेट एक्सपेंशन परिकल्पना, जो मानती है कि SSE का अनुमान लगाना कठिन है, अद्वितीय गेम अनुमान की तुलना में एक मजबूत (लेकिन निकटता से संबंधित) धारणा है।<ref name = rs10>
+यूनिक लेबल कवर समस्या से निकटता से संबंधित है, लघु सेट विस्तार (एसएसई) समस्या: ग्राफ <math>G = (V,E)</math> दिया गया, वर्टिकल का लघु सेट (<math>n/\log(n)</math> आकार का) खोजें; जिसका एज विस्तार न्यूनतम है। यह ज्ञात है कि यदि एसएसई का अनुमान लगाना कठिन है, तो अद्वितीय लेबल कवर भी ऐसा ही है। इसलिए, लघु सेट विस्तार परिकल्पना, जो मानती है कि एसएसई का अनुमान लगाना कठिन है, अद्वितीय खेल अनुमान की तुलना में कठोर (लेकिन निकटता से संबंधित) धारणा है।<ref name="rs10">
 {{cite conference
   | first1 = Prasad |last1=Raghavendra
@@ Line 256: / Line 236: @@
   | pages = 755–764
   | title = 42nd Annual ACM Symposium on theory of Computing (STOC) 2010
-  | year = 2010}}</ref>
+  | year = 2010}}</ref> कुछ सन्निकटन समस्याओं को एसएसई-कठोर के रूप में जाना जाता है<ref>{{cite journal
-कुछ सन्निकटन समस्याओं को एसएसई-हार्ड के रूप में जाना जाता है<ref>{{cite journal
   | first1 = Yu |last1=Wu
   | first2 = Per |last2=Austrin
@@ Line 268: / Line 247: @@
   | volume = 49
   | year = 2014| doi-access = free
-  }}</ref> (अर्थात कम से कम उतना ही मुश्किल जितना अनुमानित एसएसई)।
+  }}</ref> (अर्थात कम से कम उतना ही जटिल जितना अनुमानित एसएसई)।
-=== 3SUM अनुमान ===
+=== 3एसयूएम अनुमान ===
-{{Main|3SUM}}
+{{Main|3एसयूएम}}
-का एक सेट दिया <math>n</math> संख्याएँ, 3SUM समस्या पूछती है कि क्या संख्याओं का एक त्रिक है जिसका योग शून्य है।
-SUM के लिए एक द्विघात-समय एल्गोरिथ्म है, और यह अनुमान लगाया गया है कि कोई भी एल्गोरिथ्म वास्तव में उप-द्विघात समय में 3SUM को हल नहीं कर सकता है:
+<math>n</math> संख्याओं के सेट को देखते हुए, 3एसयूएम समस्या पूछती है कि क्या संख्याओं का त्रिक है, जिसका योग शून्य है। 3एसयूएम के लिए द्विघात-समय एल्गोरिथ्म है, और यह अनुमान लगाया गया है कि कोई भी एल्गोरिथ्म 3एसयूएम को "वास्तव में उप-द्विघात समय" में हल नहीं कर सकता है: 3एसयूएम अनुमान कम्प्यूटेशनल कठोरता धारणा है कि 3एसयूएम के लिए कोई <math>O(n^{2-\varepsilon})</math> समय एल्गोरिदम नहीं हैं (किसी भी स्थिरांक के लिए <math>\varepsilon > 0</math>)। यह अनुमान कई समस्याओं के लिए निकट-द्विघात निचली सीमा को प्रमाणित करने के लिए उपयोगी है, अधिकतर [[कम्प्यूटेशनल ज्यामिति]] से उपयोगी है।<ref>
-SUM अनुमान कम्प्यूटेशनल कठोरता धारणा है कि नहीं हैं <math>O(n^{2-\varepsilon})</math>3SUM के लिए समय एल्गोरिदम (किसी भी स्थिरांक के लिए <math>\varepsilon > 0</math>).
-यह अनुमान कई समस्याओं के लिए निकट-द्विघात निचली सीमा को साबित करने के लिए उपयोगी है, ज्यादातर [[कम्प्यूटेशनल ज्यामिति]] से।<ref>
 {{cite conference
 | last1 = Vassilevska Williams | first1 = Virginia | author1-link = Virginia Vassilevska Williams
@@ Line 283: / Line 260: @@
   | year = 2018
 }}</ref>
@@ Line 292: / Line 270: @@
 {{Computational hardness assumptions}}
-[[Category: क्रिप्टोग्राफी का सिद्धांत]] [[Category: कम्प्यूटेशनल संख्या सिद्धांत]] [[Category: कम्प्यूटेशनल कठोरता मान्यताओं]]
-[[Category: Machine Translated Page]]
+[[Category:Articles with hatnote templates targeting a nonexistent page]]
+[[Category:Collapse templates]]
 [[Category:Created On 11/05/2023]]
+[[Category:Lua-based templates]]
+[[Category:Machine Translated Page]]
+[[Category:Navigational boxes| ]]
+[[Category:Navigational boxes without horizontal lists]]
+[[Category:Pages with script errors]]
+[[Category:Sidebars with styles needing conversion]]
+[[Category:Template documentation pages|Documentation/doc]]
+[[Category:Templates Translated in Hindi]]
+[[Category:Templates Vigyan Ready]]
+[[Category:Templates generating microformats]]
+[[Category:Templates that add a tracking category]]
+[[Category:Templates that are not mobile friendly]]
+[[Category:Templates that generate short descriptions]]
+[[Category:Templates using TemplateData]]
+[[Category:Wikipedia metatemplates]]
+[[Category:कम्प्यूटेशनल कठोरता मान्यताओं]]
+[[Category:कम्प्यूटेशनल संख्या सिद्धांत]]
+[[Category:क्रिप्टोग्राफी का सिद्धांत]]

Anonymous

Search

कम्प्यूटेशनल कठोरता धारणा: Difference between revisions

Latest revision as of 09:43, 26 May 2023

कठोरता धारणाओं की तुलना

कठोरता धारणाओं की शक्ति

औसत स्थिति के विपरीत सबसे खराब-स्थिति धारणायें

मिथ्याकरण

सामान्य क्रिप्टोग्राफ़िक कठोरता धारणाएँ

पूर्णांक गुणनखंड

आरएसए समस्या

अवशिष्टता की समस्या

फी-छिपी धारणा

असतत लॉग समस्या (डीएलपी)

बहुरेखीय मानचित्र

लैटिस की समस्या

गैर-क्रिप्टोग्राफ़िक कठोरता धारणाएँ

सी-कठोर समस्याएं

घातीय समय परिकल्पना (ईटीएच) और वेरिएंट्स

औसत-स्थिति कठोरता धारणा

अद्वितीय खेल

लघु सेट विस्तार

3एसयूएम अनुमान

यह भी देखें

संदर्भ

Navigation

Wiki tools

Page tools

Other projects

Categories