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

Revision as of 21:51, 21 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] यह कुछ जाली आधारित क्रिप्टोग्राफी बनाता है | लैटिस-आधारित क्रिप्टोप्रणाली पोस्ट-क्वांटम क्रिप्टोग्राफी के लिए उम्मीदवार हैं।

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

NTRU (NTRUEncrypt और NTRUSign दोनों)
होमोमोर्फिक एन्क्रिप्शन के लिए अधिकांश उम्मीदवार

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

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

सी-हार्ड समस्याएं

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

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

घातीय समय परिकल्पना (ETH) की कठोरता धारणाओं की #शक्ति है $P\neq NP$ कठोरता धारणा, जो अनुमान लगाती है कि न केवल बूलियन संतुष्टि समस्या में बहुपद समय एल्गोरिथ्म नहीं है, बल्कि इसके लिए घातीय समय की आवश्यकता है ( $2^{\Omega (n)}$ ).^[17] एक और भी कठोर धारणा, जिसे एक्सपोनेंशियल टाइम परिकल्पना (SETH) के रूप में जाना जाता है, यह अनुमान लगाती है कि बूलियन संतुष्टि समस्या | $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$ -क्लिक (जो अद्वितीय w.h.p. है)।^[20] एक अन्य महत्वपूर्ण उदाहरण उरीएल फीगे की परिकल्पना है, जो बूलियन संतुष्टि समस्या के यादृच्छिक उदाहरणों के बारे में एक कम्प्यूटेशनल कठोरता धारणा है | 3-एसएटी (चर के खंड के विशिष्ट अनुपात को बनाए रखने के लिए नमूना)।^[21] औसत-स्थिति कम्प्यूटेशनल कठोरता धारणाएँ आँकड़ों जैसे अनुप्रयोगों में औसत-स्थिति कठोरता को प्रमाणित करने के लिए उपयोगी होती हैं, जहाँ इनपुट पर प्राकृतिक वितरण होता है।^[22] इसके अतिरिक्त, प्लांटेड क्लिक हार्डनेस धारणा का उपयोग अन्य समस्याओं के बहुपद और अर्ध-बहुपद वर्स्ट-स्थिति टाइम जटिलता के बीच अंतर करने के लिए भी किया गया है,^[23] इसी तरह #Exponential Time Hypothesis (ETH) और वेरिएंट।

अनोखा खेल

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

छोटा सेट विस्तार

यूनिक लेबल कवर समस्या से निकटता से संबंधित है स्मॉल सेट एक्सपेंशन (एसएसई) समस्या: एक ग्राफ दिया गया $G=(V,E)$ , वर्टिकल का एक छोटा सेट खोजें (आकार का $n/\log(n)$ ) जिसका विस्तारक ग्राफ#एज विस्तार न्यूनतम है।

यह ज्ञात है कि यदि एसएसई का अनुमान लगाना कठिन है, तो अद्वितीय लेबल कवर भी ऐसा ही है। इसलिए, स्मॉल सेट एक्सपेंशन परिकल्पना, जो मानती है कि एसएसई का अनुमान लगाना कठिन है, अद्वितीय गेम अनुमान की तुलना में एक कठोर (लेकिन निकटता से संबंधित) धारणा है।^[25] कुछ सन्निकटन समस्याओं को एसएसई-हार्ड के रूप में जाना जाता है^[26] (अर्थात कम से कम उतना ही मुश्किल जितना अनुमानित एसएसई)।

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

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

@@ 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|सबसे अच्छी, सबसे खराब और औसत स्थिति}}
-औसत-केस धारणा कहती है कि कुछ स्पष्ट वितरण से अधिकांश उदाहरणों पर एक विशिष्ट समस्या कठिन है, जबकि सबसे खराब-केस धारणा केवल यह कहती है कि समस्या कुछ उदाहरणों पर कठिन है। किसी समस्या के लिए, औसत-स्थिति की कठोरता का तात्पर्य सबसे खराब-कठोरता से है, इसलिए एक #औसत-स्थिति की कठोरता धारणा|औसत-स्थिति की कठोरता धारणा एक ही समस्या के लिए सबसे खराब-कठोरता धारणा से अधिक कठोर है।
+औसत-स्थिति धारणा कहती है कि कुछ स्पष्ट वितरण से अधिकांश उदाहरणों पर एक विशिष्ट समस्या कठिन है, जबकि सबसे खराब-स्थिति धारणा केवल यह कहती है कि समस्या कुछ उदाहरणों पर कठिन है। किसी समस्या के लिए, औसत-स्थिति की कठोरता का तात्पर्य सबसे खराब-कठोरता से है, इसलिए औसत-स्थिति की कठोरता धारणा एक ही समस्या के लिए सबसे खराब-कठोरता धारणा से अधिक कठोर है।
-इसके अतिरिक्त, अतुलनीय समस्याओं के लिए भी, #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="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> सौभाग्य से, क्रिप्टोग्राफी में उपयोग की जाने वाली कई औसत-केस धारणाएं (#आरएसए समस्या, #डिस्क्रीट लॉग समस्या (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>
+ध्यान दें, चूँकि, अधिकांश क्रिप्टोग्राफ़िक अनुप्रयोगों में, यह जानना कि किसी समस्या का कुछ कठिन उदाहरण है (अर्थात सबसे खराब स्थिति में समस्या कठिन है) व्यर्थ है क्योंकि यह हमें कठिन उदाहरण उत्पन्न करने की विधि प्रदान नहीं करता है।<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>
 === [[मिथ्याकरण]] ===
-कम्प्यूटेशनल कठोरता धारणा की एक वांछित विशेषता मिथ्याकरण है, अर्थात यदि धारणा झूठी थी, तो इसे प्रमाणित करना संभव होगा।
+कम्प्यूटेशनल कठोरता धारणा की एक वांछित विशेषता मिथ्याकरण है, अर्थात यदि धारणा असत्य थी, तो इसे प्रमाणित करना संभव होगा। विशेष रूप से, {{harvtxt|नौर|2003}} ने क्रिप्टोग्राफ़िक मिथ्याकरण की एक औपचारिक धारणा प्रस्तुत की थी।<ref>{{cite conference
-विशेष रूप से, {{harvtxt|Naor|2003}} ने क्रिप्टोग्राफ़िक मिथ्याकरण की एक औपचारिक धारणा पेश की।<ref>{{cite conference
   | last = Naor | first = Moni
   | editor-last = Boneh | editor-first = Dan
@@ Line 42: / Line 37: @@
   | volume = 2729
   | year = 2003| doi-access = free
-  }}</ref>
+  }}</ref> मोटे तौर पर, यदि एक कम्प्यूटेशनल कठोरता धारणा को चुनौती के रूप में तैयार किया जा सकता है ,तो इसे अनुचित माना जाता है: एक विरोधी और एक कुशल सत्यापनकर्ता के बीच एक इंटरैक्टिव प्रोटोकॉल रहता है, जहां एक कुशल विरोधी सत्यापनकर्ता को यह स्वीकार करने के लिए सहमत कर सकता है यदि और केवल यदि धारणा अनुचित है।
-मोटे तौर पर, एक कम्प्यूटेशनल कठोरता धारणा को गलत माना जाता है अगर इसे चुनौती के रूप में तैयार किया जा सकता है:
-एक विरोधी और एक कुशल सत्यापनकर्ता के बीच एक इंटरैक्टिव प्रोटोकॉल,
-जहां एक कुशल विरोधी सत्यापनकर्ता को स्वीकार करने के लिए राजी कर सकता है अगर और केवल अगर धारणा गलत है।
 == सामान्य क्रिप्टोग्राफ़िक कठोरता धारणाएँ ==
-उपयोग में कई क्रिप्टोग्राफ़िक कठोरता धारणाएँ हैं। यह कुछ सबसे सामान्य लोगों की सूची है, और कुछ क्रिप्टोग्राफ़िक प्रोटोकॉल जो उनका उपयोग करते हैं।
+उपयोग में कई क्रिप्टोग्राफ़िक कठोरता धारणाएँ हैं। यह कुछ सबसे सामान्य धारणाओं की सूची है, और कुछ क्रिप्टोग्राफ़िक प्रोटोकॉल जो उनका उपयोग करते हैं।
 === पूर्णांक गुणनखंड ===
 {{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>).
-कई क्रिप्टोग्राफ़िक प्रोटोकॉल की सुरक्षा इस धारणा पर निर्भर करती है कि पूर्णांक गुणनखंडन कठिन है (अर्थात बहुपद समय में हल नहीं किया जा सकता है)।
-क्रिप्टोप्रणाली जिनकी सुरक्षा इस धारणा के बराबर है, में [[राबिन क्रिप्टोसिस्टम|राबिन क्रिप्टोप्रणाली]] और ओकामोटो-उचियामा क्रिप्टोप्रणाली सम्मिलित हैं।
-कई और क्रिप्टोप्रणाली कठोर धारणाओं पर विश्वास करते हैं जैसे #आरएसए समस्या, #अवशेष समस्याएं, और #Phi-hiding धारणा|Phi-hiding।
 ==== आरएसए समस्या ====
   {{Main|आरएसए समस्या}}
-एक समग्र संख्या दी गई है <math>n</math>, प्रतिपादक <math>e</math> और संख्या <math>c := m^e (\mathrm{mod}\; n)</math>, आरएसए समस्या का पता लगाना है <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|उच्च अवशेषता समस्या}}
-एक समग्र संख्या दी गई है <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>.
+*गोल्डवेसर-मिकाली क्रिप्टोप्रणाली (द्विघात पुनर्वितरण समस्या)
-अवशिष्टता समस्याओं की कठोरता पर विश्वास करने वाले कुछ क्रिप्टो प्रणाली में सम्मिलित हैं:
+* [[ब्लम ब्लम डंप जनरेटर|ब्लम ब्लम शुब जनरेटर]] (द्विघात पुनर्वितरण समस्या)
-*Goldwaएसएसईr–Micali क्रिप्टोप्रणाली (द्विघात पुनर्वितरण समस्या)
+*[[पैलियर क्रिप्टोसिस्टम|पैलियर क्रिप्टोप्रणाली]] (निर्णायक संयुक्त अवशिष्टता समस्या)
-* [[ब्लम ब्लम डंप जनरेटर]] (द्विघात पुनर्वितरण समस्या)
+*[[ बेनलोह क्रिप्टोसिस्टम |बेनालोह क्रिप्टोप्रणाली]]  (उच्च अवशिष्टता समस्या)
-*[[पैलियर क्रिप्टोसिस्टम|पैलियर क्रिप्टोप्रणाली]] (निर्णायक समग्र अवशिष्टता समस्या)
-*[[ बेनलोह क्रिप्टोसिस्टम | बेनलोह क्रिप्टोप्रणाली]]  (उच्च अवशिष्टता समस्या)
 *नाकाचे-स्टर्न क्रिप्टोप्रणाली (उच्च अवशिष्टता समस्या)
 ==== फी-छिपी धारणा ====
 {{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|असतत लघुगणक}}
-दिए गए तत्व <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 एन्क्रिप्शन|एलगामल एन्क्रिप्शन]] (जो अभी तक कठोर निर्णायक डिफी-हेलमैन (डीडीएच) संस्करण पर निर्भर करता है) सम्मिलित हैं।
 ==== बहुरेखीय मानचित्र ====
@@ Line 97: / Line 80: @@
 {{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> <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>
-बहुरेखीय कठोरता मान्यताओं पर विश्वास करने वाले कुछ क्रिप्टो प्रणाली में सम्मिलित हैं:
+बहुरेखीय कठोरता धारणाओं पर विश्वास करने वाले कुछ क्रिप्टो प्रणाली में सम्मिलित हैं:
 * [[बोन-फ्रैंकलिन योजना]] (ब्लिनियर डिफी-हेलमैन)
 * बोनेह-लिन-शचम (ब्लिनियर डिफी-हेलमैन)
@@ Line 142: / Line 125: @@
 == गैर-क्रिप्टोग्राफ़िक कठोरता धारणाएँ ==
-साथ ही उनके क्रिप्टोग्राफ़िक अनुप्रयोगों के साथ-साथ कठोरता मान्यताओं का उपयोग कम्प्यूटेशनल जटिलता सिद्धांत में गणितीय बयानों के सबूत प्रदान करने के लिए किया जाता है जो बिना शर्त प्रमाणित करना मुश्किल होता है। इन अनुप्रयोगों में, कोई यह प्रमाणित करता है कि कठोरता धारणा कुछ वांछित जटिलता-सैद्धांतिक कथन का अर्थ है, यह प्रमाणित करने के अतिरिक्त कि कथन स्वयं सत्य है। इस प्रकार की सबसे प्रसिद्ध धारणा यह है कि पी बनाम एनपी समस्या|पी ≠ एनपी,<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
+साथ ही उनके क्रिप्टोग्राफ़िक अनुप्रयोगों के साथ-साथ कठोरता धारणाओं का उपयोग कम्प्यूटेशनल जटिलता सिद्धांत में गणितीय बयानों के सबूत प्रदान करने के लिए किया जाता है जो बिना शर्त प्रमाणित करना मुश्किल होता है। इन अनुप्रयोगों में, कोई यह प्रमाणित करता है कि कठोरता धारणा कुछ वांछित जटिलता-सैद्धांतिक कथन का अर्थ है, यह प्रमाणित करने के अतिरिक्त कि कथन स्वयं सत्य है। इस प्रकार की सबसे प्रसिद्ध धारणा यह है कि पी बनाम एनपी समस्या|पी ≠ एनपी,<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 163: / 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}}
-घातीय समय परिकल्पना (ETH) की कठोरता मान्यताओं की #शक्ति है <math>P \neq NP</math> कठोरता धारणा, जो अनुमान लगाती है कि न केवल [[बूलियन संतुष्टि समस्या]] में बहुपद समय एल्गोरिथ्म नहीं है, बल्कि इसके लिए घातीय समय की आवश्यकता है (<math>2^{\Omega(n)}</math>).<ref>{{cite conference
+घातीय समय परिकल्पना (ETH) की कठोरता धारणाओं की #शक्ति है <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 212: / Line 195: @@
   | year = 2002
 }}</ref>
-औसत-केस कम्प्यूटेशनल कठोरता धारणाएँ आँकड़ों जैसे अनुप्रयोगों में औसत-केस कठोरता को प्रमाणित करने के लिए उपयोगी होती हैं, जहाँ इनपुट पर प्राकृतिक वितरण होता है।<ref name = BR13>
+औसत-स्थिति कम्प्यूटेशनल कठोरता धारणाएँ आँकड़ों जैसे अनुप्रयोगों में औसत-स्थिति कठोरता को प्रमाणित करने के लिए उपयोगी होती हैं, जहाँ इनपुट पर प्राकृतिक वितरण होता है।<ref name = BR13>
 {{cite conference
 | last1 = Berthet | first1 = Quentin
@@ Line 222: / Line 205: @@
   | year = 2013
 }}</ref>
-इसके अतिरिक्त, प्लांटेड क्लिक हार्डनेस धारणा का उपयोग अन्य समस्याओं के बहुपद और अर्ध-बहुपद वर्स्ट-केस टाइम जटिलता के बीच अंतर करने के लिए भी किया गया है,<ref name = HK11>{{cite journal
+इसके अतिरिक्त, प्लांटेड क्लिक हार्डनेस धारणा का उपयोग अन्य समस्याओं के बहुपद और अर्ध-बहुपद वर्स्ट-स्थिति टाइम जटिलता के बीच अंतर करने के लिए भी किया गया है,<ref name = HK11>{{cite journal
   | last1 = Hazan | first1 = Elad
   | last2 = Krauthgamer | first2 = Robert
@@ Line 282: / Line 265: @@
 एसयूएम के लिए एक द्विघात-समय एल्गोरिथ्म है, और यह अनुमान लगाया गया है कि कोई भी एल्गोरिथ्म वास्तव में उप-द्विघात समय में 3एसयूएम को हल नहीं कर सकता है:
 एसयूएम अनुमान कम्प्यूटेशनल कठोरता धारणा है कि नहीं हैं <math>O(n^{2-\varepsilon})</math>3एसयूएम के लिए समय एल्गोरिदम (किसी भी स्थिरांक के लिए <math>\varepsilon > 0</math>).
-यह अनुमान कई समस्याओं के लिए निकट-द्विघात निचली सीमा को प्रमाणित करने के लिए उपयोगी है, ज्यादातर [[कम्प्यूटेशनल ज्यामिति]] से।<ref>
+यह अनुमान कई समस्याओं के लिए निकट-द्विघात निचली सीमा को प्रमाणित करने के लिए उपयोगी है, अधिकतर [[कम्प्यूटेशनल ज्यामिति]] से।<ref>
 {{cite conference
 | last1 = Vassilevska Williams | first1 = Virginia | author1-link = Virginia Vassilevska Williams

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

Anonymous

Search

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

Namespaces

More

Page actions

Revision as of 21:51, 21 May 2023

Contents

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

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

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

मिथ्याकरण

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

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

आरएसए समस्या

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

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

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

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

जाली की समस्या

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

सी-हार्ड समस्याएं

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

औसत-मामला कठोरता धारणा

अनोखा खेल

छोटा सेट विस्तार

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

यह भी देखें

संदर्भ

Navigation

Navigation

Wiki tools

Wiki tools

Anonymous

Search

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

Revision as of 21:51, 21 May 2023

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

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

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

मिथ्याकरण

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

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

आरएसए समस्या

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

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

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

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

जाली की समस्या

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

सी-हार्ड समस्याएं

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

औसत-मामला कठोरता धारणा

अनोखा खेल

छोटा सेट विस्तार

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

यह भी देखें

संदर्भ

Navigation

Wiki tools

Page tools

Other projects

Categories