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

Revision as of 20:39, 21 May 2023

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

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

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

कठोरता मान्यताओं की तुलना

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

कठोरता मान्यताओं की ताकत

हम कहते हैं कि धारणा $A$ धारणा से ज्यादा कठोर है $B$ कब $A$ तात्पर्य $B$ (और बातचीत गलत है या ज्ञात नहीं है)।

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

औसत स्थिति के विपरीत सबसे खराब-स्थिति मान्यताएँ

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

इसके अतिरिक्त, अतुलनीय समस्याओं के लिए भी, #Exponential Time Hypothesis (ETH) और वेरिएंट जैसी धारणा को अधिकांशतः माना जाता है लगाया गुट की तरह #औसत-स्थिति की कठोरता धारणा|औसत-स्थिति की धारणा के लिए उत्तम।^[1]

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

मिथ्याकरण

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

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

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

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

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

आरएसए समस्या

एक समग्र संख्या दी गई है $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$ . अवशिष्टता समस्याओं की कठोरता पर विश्वास करने वाले कुछ क्रिप्टो प्रणाली में सम्मिलित हैं:

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

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

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

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

दिए गए तत्व $a$ और $b$ एक समूह से (गणित) $G$ असतत लॉग समस्या एक पूर्णांक के लिए पूछती है $k$ ऐसा है कि $a=b^{k}$ . असतत लॉग समस्या को पूर्णांक फ़ैक्टराइज़ेशन के साथ तुलना करने के लिए नहीं जाना जाता है, लेकिन उनकी कम्प्यूटेशनल जटिलता असतत लघुगणक # पूर्णांक फ़ैक्टराइज़ेशन के साथ तुलना है।

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

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

एक बहुरेखीय मानचित्र एक कार्य $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}}
-[[कम्प्यूटेशनल जटिलता सिद्धांत]] में, एक कम्प्यूटेशनल कठोरता धारणा परिकल्पना है कि एक विशेष समस्या को कुशलतापूर्वक हल नहीं किया जा सकता है (जहां 'कुशलता' का अर्थ आमतौर पर बहुपद समय में होता है)। यह ज्ञात नहीं है कि अनिवार्य रूप से किसी उपयोगी समस्या के लिए (बिना शर्त) कठोरता को कैसे सिद्ध किया जाए। इसके बजाय, कंप्यूटर वैज्ञानिक एक नई या जटिल समस्या की कठोरता को औपचारिक रूप से किसी समस्या के बारे में कम्प्यूटेशनल कठोरता धारणा से संबंधित करने के लिए रिडक्शन (जटिलता) पर भरोसा करते हैं जो बेहतर समझी जाती है।
+[[कम्प्यूटेशनल जटिलता सिद्धांत]] में, एक कम्प्यूटेशनल कठोरता धारणा परिकल्पना है कि एक विशेष समस्या को कुशलतापूर्वक हल नहीं किया जा सकता है (जहां 'कुशलता' का अर्थ सामान्यतः बहुपद समय में होता है)। यह ज्ञात नहीं है कि अनिवार्य रूप से किसी उपयोगी समस्या के लिए (बिना शर्त) कठोरता को कैसे सिद्ध किया जाए। इसके अतिरिक्त, कंप्यूटर वैज्ञानिक एक नई या जटिल समस्या की कठोरता को औपचारिक रूप से किसी समस्या के बारे में कम्प्यूटेशनल कठोरता धारणा से संबंधित करने के लिए रिडक्शन (जटिलता) पर विश्वास करते हैं जो उत्तम समझी जाती है।
-[[क्रिप्टोग्राफी]] में कम्प्यूटेशनल कठोरता मान्यताओं का विशेष महत्व है। क्रिप्टोग्राफ़ी में एक प्रमुख लक्ष्य क्रिप्टोग्राफ़िक आदिमों को साबित करने योग्य सुरक्षा के साथ बनाना है। कुछ मामलों में, [[क्रिप्टोग्राफिक आदिम]] में [[सूचना सैद्धांतिक सुरक्षा]] पाई जाती है; वन-टाइम पैड एक सामान्य उदाहरण है। हालाँकि, सूचना सिद्धांत सुरक्षा हमेशा प्राप्त नहीं की जा सकती है; ऐसे मामलों में, क्रिप्टोग्राफ़र कम्प्यूटेशनल सुरक्षा में वापस आ जाते हैं। मोटे तौर पर, इसका मतलब यह है कि ये सिस्टम सुरक्षित हैं ''यह मानते हुए कि कोई भी विरोधी कम्प्यूटेशनल रूप से सीमित हैं'', क्योंकि सभी विरोधी व्यवहार में हैं।
+[[क्रिप्टोग्राफी]] में कम्प्यूटेशनल कठोरता मान्यताओं का विशेष महत्व है। क्रिप्टोग्राफ़ी में एक प्रमुख लक्ष्य क्रिप्टोग्राफ़िक आदिमों को प्रमाणित करने योग्य सुरक्षा के साथ बनाना है। कुछ स्थितियों में, [[क्रिप्टोग्राफिक आदिम]] में [[सूचना सैद्धांतिक सुरक्षा]] पाई जाती है; वन-टाइम पैड एक सामान्य उदाहरण है। चूँकि, सूचना सिद्धांत सुरक्षा सदैव प्राप्त नहीं की जा सकती है; ऐसी स्थितियों में, क्रिप्टोग्राफ़र कम्प्यूटेशनल सुरक्षा में वापस आ जाते हैं। मोटे तौर पर, इसका अर्थ यह है कि ये प्रणाली सुरक्षित हैं यह मानते हुए कि कोई भी विरोधी कम्प्यूटेशनल रूप से सीमित हैं, क्योंकि सभी विरोधी व्यवहार में हैं।
 कम्प्यूटेशनल कठोरता धारणाएँ एल्गोरिथम डिजाइनरों के मार्गदर्शन के लिए भी उपयोगी हैं: एक साधारण एल्गोरिथ्म एक अच्छी तरह से अध्ययन की गई कम्प्यूटेशनल कठोरता धारणा का खंडन करने की संभावना नहीं है जैसे कि पी बनाम एनपी समस्या | पी ≠ एनपी।
@@ Line 10: / Line 10: @@
 === कठोरता मान्यताओं की ताकत ===
-हम कहते हैं कि धारणा <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> अभी भी उपयोग करने के लिए सुरक्षित हो सकता है।
-इस प्रकार क्रिप्टोग्राफ़िक प्रोटोकॉल तैयार करते समय, सबसे कमजोर संभावित धारणाओं का उपयोग करके सुरक्षा को साबित करने में सक्षम होने की उम्मीद है।
+इस प्रकार क्रिप्टोग्राफ़िक प्रोटोकॉल तैयार करते समय, सबसे कमजोर संभावित धारणाओं का उपयोग करके सुरक्षा को प्रमाणित करने में सक्षम होने की उम्मीद है।
+===औसत स्थिति के विपरीत सबसे खराब-स्थिति मान्यताएँ ===
+{{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="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>
-===औसत-मामला बनाम सबसे खराब-मामला मान्यताओं===
-{{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|Naor|2003}} ने क्रिप्टोग्राफ़िक मिथ्याकरण की एक औपचारिक धारणा पेश की।<ref>{{cite conference
   | last = Naor | first = Moni
@@ Line 44: / Line 49: @@
 == सामान्य क्रिप्टोग्राफ़िक कठोरता धारणाएँ ==
-उपयोग में कई क्रिप्टोग्राफ़िक कठोरता धारणाएँ हैं। यह कुछ सबसे आम लोगों की सूची है, और कुछ क्रिप्टोग्राफ़िक प्रोटोकॉल जो उनका उपयोग करते हैं।
+उपयोग में कई क्रिप्टोग्राफ़िक कठोरता धारणाएँ हैं। यह कुछ सबसे सामान्य लोगों की सूची है, और कुछ क्रिप्टोग्राफ़िक प्रोटोकॉल जो उनका उपयोग करते हैं।
 === पूर्णांक गुणनखंड ===
-{{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>).
 कई क्रिप्टोग्राफ़िक प्रोटोकॉल की सुरक्षा इस धारणा पर निर्भर करती है कि पूर्णांक गुणनखंडन कठिन है (अर्थात बहुपद समय में हल नहीं किया जा सकता है)।
-क्रिप्टोसिस्टम जिनकी सुरक्षा इस धारणा के बराबर है, में [[राबिन क्रिप्टोसिस्टम]] और ओकामोटो-उचियामा क्रिप्टोसिस्टम शामिल हैं।
+क्रिप्टोप्रणाली जिनकी सुरक्षा इस धारणा के बराबर है, में [[राबिन क्रिप्टोसिस्टम|राबिन क्रिप्टोप्रणाली]] और ओकामोटो-उचियामा क्रिप्टोप्रणाली सम्मिलित हैं।
-कई और क्रिप्टोसिस्टम मजबूत धारणाओं पर भरोसा करते हैं जैसे #RSA समस्या, #अवशेष समस्याएं, और #Phi-hiding धारणा|Phi-hiding।
+कई और क्रिप्टोप्रणाली कठोर धारणाओं पर विश्वास करते हैं जैसे #आरएसए समस्या, #अवशेष समस्याएं, और #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,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 क्रिप्टोसिस्टम (द्विघात पुनर्वितरण समस्या)
+*Goldwaएसएसईr–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>a</math> और <math>b</math> एक समूह से (गणित) <math>G</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>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>
-बहुरेखीय कठोरता मान्यताओं पर भरोसा करने वाले कुछ क्रिप्टो सिस्टम में शामिल हैं:
+बहुरेखीय कठोरता मान्यताओं पर विश्वास करने वाले कुछ क्रिप्टो प्रणाली में सम्मिलित हैं:
 * [[बोन-फ्रैंकलिन योजना]] (ब्लिनियर डिफी-हेलमैन)
 * बोनेह-लिन-शचम (ब्लिनियर डिफी-हेलमैन)
@@ Line 107: / Line 111: @@
 {{Main|Lattice problem}}
 जाली पर सबसे मौलिक कम्प्यूटेशनल समस्या है जाली समस्या # सबसे छोटी वेक्टर समस्या (एसवीपी) | सबसे छोटी वेक्टर समस्या (एसवीपी): एक जाली दी गई <math>L</math>, सबसे छोटा गैर-शून्य वेक्टर खोजें <math>v \in L</math>.
-अधिकांश क्रिप्टोसिस्टम्स को एसवीपी के रूपों पर मजबूत धारणाओं की आवश्यकता होती है, जैसे लैटिस समस्या # सबसे छोटी स्वतंत्र वैक्टर समस्या (एसआईवीपी) | सबसे छोटी स्वतंत्र वैक्टर समस्या (एसआईवीपी), जाली समस्या # गैपएसवीपी,<ref name = peikert09>{{cite conference
+अधिकांश क्रिप्टोप्रणाली्स को एसवीपी के रूपों पर कठोर धारणाओं की आवश्यकता होती है, जैसे लैटिस समस्या # सबसे छोटी स्वतंत्र वैक्टर समस्या (एसआईवीपी) | सबसे छोटी स्वतंत्र वैक्टर समस्या (एसआईवीपी), जाली समस्या # गैपएसवीपी,<ref name = peikert09>{{cite conference
   | first = Chris |last=Peikert
   | contribution = Public-key cryptosystems from the worst-case shortest vector problem: extended abstract
@@ Line 122: / Line 126: @@
   | 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 131: / Line 135: @@
   }}</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]] दोनों)
 * [[होमोमोर्फिक एन्क्रिप्शन]] के लिए अधिकांश उम्मीदवार
 == गैर-क्रिप्टोग्राफ़िक कठोरता धारणाएँ ==
-साथ ही उनके क्रिप्टोग्राफ़िक अनुप्रयोगों के साथ-साथ कठोरता मान्यताओं का उपयोग कम्प्यूटेशनल जटिलता सिद्धांत में गणितीय बयानों के सबूत प्रदान करने के लिए किया जाता है जो बिना शर्त साबित करना मुश्किल होता है। इन अनुप्रयोगों में, कोई यह साबित करता है कि कठोरता धारणा कुछ वांछित जटिलता-सैद्धांतिक कथन का अर्थ है, यह साबित करने के बजाय कि कथन स्वयं सत्य है। इस प्रकार की सबसे प्रसिद्ध धारणा यह है कि पी बनाम एनपी समस्या|पी ≠ एनपी,<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 159: / Line 163: @@
 === सी-हार्ड समस्याएं ===
-कई वर्स्ट-केस जटिलता|वर्स्ट-केस कम्प्यूटेशनल समस्याओं को कुछ [[जटिलता वर्ग]] के लिए कठिन या [[पूर्ण (जटिलता)]] के रूप में जाना जाता है <math>C</math>, विशेष रूप से [[ एनपी-कठोरता ]]|एनपी-हार्ड (लेकिन अक्सर [[पीएसपीएसीई-पूर्ण समस्याओं की सूची]]|पीएसपीएसीई-हार्ड, [[पीपीएडी-पूर्ण समस्याओं की सूची]]|पीपीएडी-हार्ड, आदि)। इसका मतलब यह है कि वे कम से कम उतने ही कठिन हैं जितनी कि कक्षा की कोई समस्या <math>C</math>.
+कई वर्स्ट-केस जटिलता|वर्स्ट-केस कम्प्यूटेशनल समस्याओं को कुछ [[जटिलता वर्ग]] के लिए कठिन या [[पूर्ण (जटिलता)]] के रूप में जाना जाता है <math>C</math>, विशेष रूप से [[ एनपी-कठोरता ]]|एनपी-हार्ड (लेकिन अधिकांशतः [[पीएसपीएसीई-पूर्ण समस्याओं की सूची]]|पीएसपीएसीई-हार्ड, [[पीपीएडी-पूर्ण समस्याओं की सूची]]|पीपीएडी-हार्ड, आदि)। इसका अर्थ यह है कि वे कम से कम उतने ही कठिन हैं जितनी कि कक्षा की कोई समस्या <math>C</math>.
 यदि कोई समस्या है <math>C</math>-हार्ड (बहुपद समय में कमी के संबंध में), तो इसे बहुपद-समय एल्गोरिदम द्वारा हल नहीं किया जा सकता जब तक कि कम्प्यूटेशनल कठोरता धारणा नहीं <math>P \neq C</math> गलत है।
@@ Line 171: / Line 175: @@
   | 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> एक और भी कठोर धारणा, जिसे एक्सपोनेंशियल टाइम परिकल्पना (SETH) के रूप में जाना जाता है, यह अनुमान लगाती है कि बूलियन संतुष्टि समस्या |<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
   | last1 = Abboud | first1 = Amir
@@ Line 196: / Line 200: @@
 === औसत-मामला कठोरता धारणा ===
-{{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>-क्लिक (जो अद्वितीय 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>
@@ Line 208: / Line 212: @@
   | year = 2002
 }}</ref>
-औसत-केस कम्प्यूटेशनल कठोरता धारणाएँ आँकड़ों जैसे अनुप्रयोगों में औसत-केस कठोरता को साबित करने के लिए उपयोगी होती हैं, जहाँ इनपुट पर प्राकृतिक वितरण होता है।<ref name = BR13>
+औसत-केस कम्प्यूटेशनल कठोरता धारणाएँ आँकड़ों जैसे अनुप्रयोगों में औसत-केस कठोरता को प्रमाणित करने के लिए उपयोगी होती हैं, जहाँ इनपुट पर प्राकृतिक वितरण होता है।<ref name = BR13>
 {{cite conference
 | last1 = Berthet | first1 = Quentin
@@ Line 232: / Line 236: @@
 === अनोखा खेल ===
-{{Main|Unique games conjecture}}
+{{Main|अनोखा खेल अनुमान}}
-अनोखा खेल अनुमान #अद्वितीय लेबल कवर समस्या एक बाधा संतुष्टि समस्या है, जहां प्रत्येक बाधा <math>C</math> दो चर शामिल हैं <math>x,y</math>, और के प्रत्येक मूल्य के लिए <math>x</math> का एक अनूठा मूल्य है <math>y</math> जो संतुष्ट करता है <math>C</math>.
+अनोखा खेल अनुमान #अद्वितीय लेबल कवर समस्या एक बाधा संतुष्टि समस्या है, जहां प्रत्येक बाधा <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 />सन्निकटन समस्याओं को अक्सर यूजीसी मानते हुए एनपी-हार्ड के रूप में जाना जाता है; ऐसी समस्याओं को यूजी-हार्ड कहा जाता है।
+यह निर्धारित करना कि क्या सभी बाधाओं को पूरा किया जा सकता है, आसान है, लेकिन यूनीक गेम कंजेक्चर (यूजीसी) का मानना है कि यह निर्धारित करना कि क्या लगभग सभी बाधाएं (<math>(1-\varepsilon)</math>-अंश, किसी भी स्थिरांक के लिए <math>\varepsilon>0</math>) संतुष्ट हो सकते हैं या उनमें से लगभग कोई नहीं (<math>\varepsilon</math>-अंश) संतुष्ट किया जा सकता है एनपी-हार्ड है।<ref name=khot10 />सन्निकटन समस्याओं को अधिकांशतः यूजीसी मानते हुए एनपी-हार्ड के रूप में जाना जाता है; ऐसी समस्याओं को यूजी-हार्ड कहा जाता है।
 विशेष रूप से, यह मानते हुए कि UGC में एक अर्ध-निश्चित प्रोग्रामिंग एल्गोरिथम है जो कई महत्वपूर्ण समस्याओं के लिए इष्टतम सन्निकटन गारंटी प्राप्त करता है।<ref name = rag08>
 {{cite conference
@@ Line 246: / Line 250: @@
 ====छोटा सेट विस्तार====
-{{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 270: / Line 276: @@
   }}</ref> (अर्थात कम से कम उतना ही मुश्किल जितना अनुमानित एसएसई)।
-=== 3SUM अनुमान ===
+=== 3एसयूएम अनुमान ===
-{{Main|3SUM}}
+{{Main|3एसयूएम}}
-का एक सेट दिया <math>n</math> संख्याएँ, 3SUM समस्या पूछती है कि क्या संख्याओं का एक त्रिक है जिसका योग शून्य है।
-SUM के लिए एक द्विघात-समय एल्गोरिथ्म है, और यह अनुमान लगाया गया है कि कोई भी एल्गोरिथ्म वास्तव में उप-द्विघात समय में 3SUM को हल नहीं कर सकता है:
+का एक सेट दिया <math>n</math> संख्याएँ, 3एसयूएम समस्या पूछती है कि क्या संख्याओं का एक त्रिक है जिसका योग शून्य है।
-SUM अनुमान कम्प्यूटेशनल कठोरता धारणा है कि नहीं हैं <math>O(n^{2-\varepsilon})</math>3SUM के लिए समय एल्गोरिदम (किसी भी स्थिरांक के लिए <math>\varepsilon > 0</math>).
+एसयूएम के लिए एक द्विघात-समय एल्गोरिथ्म है, और यह अनुमान लगाया गया है कि कोई भी एल्गोरिथ्म वास्तव में उप-द्विघात समय में 3एसयूएम को हल नहीं कर सकता है:
-यह अनुमान कई समस्याओं के लिए निकट-द्विघात निचली सीमा को साबित करने के लिए उपयोगी है, ज्यादातर [[कम्प्यूटेशनल ज्यामिति]] से।<ref>
+एसयूएम अनुमान कम्प्यूटेशनल कठोरता धारणा है कि नहीं हैं <math>O(n^{2-\varepsilon})</math>3एसयूएम के लिए समय एल्गोरिदम (किसी भी स्थिरांक के लिए <math>\varepsilon > 0</math>).
+यह अनुमान कई समस्याओं के लिए निकट-द्विघात निचली सीमा को प्रमाणित करने के लिए उपयोगी है, ज्यादातर [[कम्प्यूटेशनल ज्यामिति]] से।<ref>
 {{cite conference
 | last1 = Vassilevska Williams | first1 = Virginia | author1-link = Virginia Vassilevska Williams
@@ Line 283: / Line 290: @@
   | year = 2018
 }}</ref>

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

Anonymous

Search

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

Namespaces

More

Page actions

Revision as of 20:39, 21 May 2023

Contents

कठोरता मान्यताओं की तुलना

कठोरता मान्यताओं की ताकत

औसत स्थिति के विपरीत सबसे खराब-स्थिति मान्यताएँ

मिथ्याकरण

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

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

आरएसए समस्या

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

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

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

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

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

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

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

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

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

अनोखा खेल

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

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

यह भी देखें

संदर्भ

Navigation

Navigation

Wiki tools

Wiki tools

Anonymous

Search

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

Revision as of 20:39, 21 May 2023

कठोरता मान्यताओं की तुलना

कठोरता मान्यताओं की ताकत

औसत स्थिति के विपरीत सबसे खराब-स्थिति मान्यताएँ

मिथ्याकरण

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

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

आरएसए समस्या

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

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

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

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

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

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

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

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

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

अनोखा खेल

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

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

यह भी देखें

संदर्भ

Navigation

Wiki tools

Page tools

Other projects

Categories