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

Revision as of 00:51, 22 May 2023

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

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

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

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

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

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

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

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

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

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

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

मिथ्याकरण

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

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

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

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

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

आरएसए समस्या

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

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

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

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

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

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

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

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

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

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

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

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

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

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

।

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

अद्वितीय खेल

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

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

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

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

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

यह भी देखें

सुरक्षा स्तर

संदर्भ

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]

[21]

[22]

[23]

[24]

[25]

[26]

[27]

@@ Line 94: / Line 94: @@
 {{Main|लैटिस समस्या}}
-लैटिस पर सबसे मौलिक कम्प्यूटेशनल समस्या है,  सबसे छोटी वेक्टर समस्या (एसवीपी) है: एक लैटिस <math>L</math> दी गई, <math>v \in L</math> में सबसे छोटा गैर-शून्य वेक्टर खोजें। अधिकांश क्रिप्टोप्रणाली को एसवीपी के रूपों पर कठोर धारणाओं की आवश्यकता होती है, जैसे कि लघुतम स्वतंत्र वैक्टर समस्या (एसआईवीपी), गैपएसवीपी,<ref name="peikert09">{{cite conference
+लैटिस पर सबसे मौलिक कम्प्यूटेशनल समस्या है,  सबसे छोटी वेक्टर समस्या (एसवीपी) है: एक लैटिस <math>L</math> दी गई, <math>v \in L</math> में सबसे लघु गैर-शून्य वेक्टर खोजें। अधिकांश क्रिप्टोप्रणाली को एसवीपी के रूपों पर कठोर धारणाओं की आवश्यकता होती है, जैसे कि लघुतम स्वतंत्र वैक्टर समस्या (एसआईवीपी), गैपएसवीपी,<ref name="peikert09">{{cite conference
   | first = Chris |last=Peikert
   | contribution = Public-key cryptosystems from the worst-case shortest vector problem: extended abstract
@@ Line 100: / Line 100: @@
   | pages = 333–342
   | title = Proceedings on 41st Annual ACM Symposium on Theory of Computing (STOC)
-  | year = 2009}}</ref> या यूनीक-एसवीपी।<ref name = ad97>{{cite conference
+  | year = 2009}}</ref> या अद्वितीय-एसवीपी।<ref name = ad97>{{cite conference
   | author1-link = Miklós Ajtai | first1=Miklós|last1= Ajtai
   | author2-link = Cynthia Dwork|first2=Cynthia|last2=Dwork
@@ Line 119: / Line 119: @@
   }}</ref>
-क्वांटम कंप्यूटरों के लिए, फैक्टरिंग और असतत लॉग समस्याएं आसान हैं, लेकिन लैटिस की समस्याओं को कठिन माना जाता है।<ref name="peikert16">{{cite journal |first = Chris|last= Peikert|year= 2016|title= जाली क्रिप्टोग्राफी का एक दशक|url= https://eprint.iacr.org/2015/939|journal= Foundations and Trends in Theoretical Computer Science|volume= 10|number = 4|pages = 283–424|doi= 10.1561/0400000074}}</ref> यह कुछ [[जाली आधारित क्रिप्टोग्राफी|लैटिस आधारित क्रिप्टोग्राफी]] को [[पोस्ट-क्वांटम क्रिप्टोग्राफी]] के लिए उपयुक्त बनाता है।
+क्वांटम कंप्यूटरों के लिए, फैक्टरिंग और असतत लॉग समस्याएं सरल हैं, लेकिन लैटिस की समस्याओं को कठिन माना जाता है।<ref name="peikert16">{{cite journal |first = Chris|last= Peikert|year= 2016|title= जाली क्रिप्टोग्राफी का एक दशक|url= https://eprint.iacr.org/2015/939|journal= Foundations and Trends in Theoretical Computer Science|volume= 10|number = 4|pages = 283–424|doi= 10.1561/0400000074}}</ref> यह कुछ [[जाली आधारित क्रिप्टोग्राफी|लैटिस आधारित क्रिप्टोग्राफी]] को [[पोस्ट-क्वांटम क्रिप्टोग्राफी]] के लिए उपयुक्त बनाता है।
 लैटिस समस्याओं की कठोरता पर विश्वास करने वाले कुछ क्रिप्टो प्रणाली में सम्मिलित हैं:
-*[[NTRU]] ([[NTRUEncrypt]] और [[NTRUSign]] दोनों)
+*[[NTRU|एनटीआरयू]] ([[NTRUEncrypt|एनटीआरयूएन्क्रिप्ट]] और [[NTRUSign|एनटीआरयूसाइन]] दोनों)
-* [[होमोमोर्फिक एन्क्रिप्शन]] के लिए अधिकांश उम्मीदवार
+* पूरी तरह से [[होमोमोर्फिक एन्क्रिप्शन]] के लिए अधिकांश प्रत्याशी
 == गैर-क्रिप्टोग्राफ़िक कठोरता धारणाएँ ==
-साथ ही उनके क्रिप्टोग्राफ़िक अनुप्रयोगों के साथ-साथ कठोरता धारणाओं का उपयोग कम्प्यूटेशनल जटिलता सिद्धांत में गणितीय बयानों के सबूत प्रदान करने के लिए किया जाता है जो बिना शर्त प्रमाणित करना मुश्किल होता है। इन अनुप्रयोगों में, कोई यह प्रमाणित करता है कि कठोरता धारणा कुछ वांछित जटिलता-सैद्धांतिक कथन का अर्थ है, यह प्रमाणित करने के अतिरिक्त कि कथन स्वयं सत्य है। इस प्रकार की सबसे प्रसिद्ध धारणा यह है कि पी बनाम एनपी समस्या|पी ≠ एनपी,<ref>{{cite journal|first=Lance|last=Fortnow|author-link=Lance Fortnow|url=http://www.cs.uchicago.edu/~fortnow/papers/pnp-cacm.pdf|archive-url=https://wayback.archive-it.org/all/20110224135332/http://www.cs.uchicago.edu/~fortnow/papers/pnp-cacm.pdf|url-status=dead|archive-date=2011-02-24|title=पी बनाम एनपी समस्या की स्थिति|journal=[[Communications of the ACM]]|volume=52|year=2009|issue=9|pages=78–86|doi=10.1145/1562164.1562186|s2cid=5969255}}.</ref> लेकिन अन्य में [[घातीय समय परिकल्पना]] सम्मिलित है,<ref>{{cite book
+साथ ही उनके क्रिप्टोग्राफ़िक अनुप्रयोगों के साथ-साथ कठोरता धारणाओं का उपयोग कम्प्यूटेशनल जटिलता सिद्धांत में गणितीय उल्लेखों के प्रमाण प्रदान करने के लिए किया जाता है, जो बिना नियमों के प्रमाणित करना जटिल होता है। इन अनुप्रयोगों में, कोई यह प्रमाणित करता है कि कठोरता धारणा कुछ वांछित जटिलता-सैद्धांतिक कथन का अर्थ है, यह प्रमाणित करने के अतिरिक्त कि कथन स्वयं सत्य है। इस प्रकार की सबसे प्रसिद्ध धारणा यह है कि '''P ≠ NP''', <ref>{{cite journal|first=Lance|last=Fortnow|author-link=Lance Fortnow|url=http://www.cs.uchicago.edu/~fortnow/papers/pnp-cacm.pdf|archive-url=https://wayback.archive-it.org/all/20110224135332/http://www.cs.uchicago.edu/~fortnow/papers/pnp-cacm.pdf|url-status=dead|archive-date=2011-02-24|title=पी बनाम एनपी समस्या की स्थिति|journal=[[Communications of the ACM]]|volume=52|year=2009|issue=9|pages=78–86|doi=10.1145/1562164.1562186|s2cid=5969255}}.</ref> लेकिन अन्य में [[घातीय समय परिकल्पना]], प्लांटेड क्लिक धारणा, और [[अद्वितीय खेल अनुमान|अद्वितीय खेल धारणा]] सम्मिलित है।<ref>{{cite book
   | last = Woeginger | first = Gerhard | author-link = Gerhard J. Woeginger
   | doi = 10.1007/3-540-36478-1_17
@@ Line 134: / Line 134: @@
   | contribution = Exact algorithms for NP-hard problems: A survey
   | year = 2003
-  | volume = 2570}}.</ref> प्लांटेड गुट, और [[अद्वितीय खेल अनुमान]]।<ref name = khot10>{{cite conference
+  | volume = 2570}}.</ref><ref name = khot10>{{cite conference
   | author-link = Subhash Khot
   | last = Khot | first = Subhash
@@ Line 146: / Line 146: @@
-=== सी-हार्ड समस्याएं ===
+=== सी-कठोर समस्याएं ===
-कई वर्स्ट-स्थिति जटिलता|वर्स्ट-स्थिति कम्प्यूटेशनल समस्याओं को कुछ [[जटिलता वर्ग]] के लिए कठिन या [[पूर्ण (जटिलता)]] के रूप में जाना जाता है <math>C</math>, विशेष रूप से [[ एनपी-कठोरता ]]|एनपी-हार्ड (लेकिन अधिकांशतः [[पीएसपीएसीई-पूर्ण समस्याओं की सूची]]|पीएसपीएसीई-हार्ड, [[पीपीएडी-पूर्ण समस्याओं की सूची]]|पीपीएडी-हार्ड, आदि)। इसका अर्थ यह है कि वे कम से कम उतने ही कठिन हैं जितनी कि कक्षा की कोई समस्या <math>C</math>.
+कई सबसे खराब-स्थिति वाली कम्प्यूटेशनल समस्याओं को कुछ [[जटिलता वर्ग]] <math>C</math> के लिए कठिन या [[पूर्ण (जटिलता)|पूर्ण]] होने के लिए जाना जाता है, विशेष रूप से [[ एनपी-कठोरता | एनपी-कठोरता]] (लेकिन अधिकांशतः [[पीएसपीएसीई-पूर्ण समस्याओं की सूची|पीएसपीएसीई-कठोर]], [[पीपीएडी-पूर्ण समस्याओं की सूची|पीपीएडी-कठोर]] आदि)। इसका अर्थ यह है कि वे वर्ग <math>C</math> में किसी भी समस्या के रूप में कम से कम कठिन हैं। यदि कोई समस्या <math>C</math>-कठोर है (बहुपद समय में कमी के संबंध में), तो इसे बहुपद-समय एल्गोरिदम द्वारा हल नहीं किया जा सकता है जब तक कि कम्प्यूटेशनल कठोरता धारणा <math>P \neq C</math> असत्य है।
-यदि कोई समस्या है <math>C</math>-हार्ड (बहुपद समय में कमी के संबंध में), तो इसे बहुपद-समय एल्गोरिदम द्वारा हल नहीं किया जा सकता जब तक कि कम्प्यूटेशनल कठोरता धारणा नहीं <math>P \neq C</math> अनुचित है।
 === घातीय समय परिकल्पना (ईटीएच) और वेरिएंट्स ===
-{{Main|Exponential time hypothesis}}
+{{Main|घातीय समय परिकल्पना}}
-घातीय समय परिकल्पना (ETH) की कठोरता धारणाओं की #शक्ति है <math>P \neq NP</math> कठोरता धारणा, जो अनुमान लगाती है कि न केवल [[बूलियन संतुष्टि समस्या]] में बहुपद समय एल्गोरिथ्म नहीं है, बल्कि इसके लिए घातीय समय की आवश्यकता है (<math>2^{\Omega(n)}</math>).<ref>{{cite conference
+घातीय समय परिकल्पना (ईटीएच) <math>P \neq NP</math> की कठोरता धारणाओं का सुदृढ़ीकरण है, जो अनुमान लगता है कि न केवल [[बूलियन संतुष्टि समस्या]] में बहुपद समय एल्गोरिथ्म नहीं है, बल्कि इसके लिए घातीय समय (<math>2^{\Omega(n)}</math>) की भी आवश्यकता नही है।<ref>{{cite conference
   | last1 = Impagliazzo | first1 = Russell | author1-link = Russell Impagliazzo
   | last2 = Paturi | first2 = Ramamohan
@@ Line 159: / Line 159: @@
   | pages = 237–240
   | title = Proc. 14th IEEE Conf. on Computational Complexity
-  | year = 1999}}</ref> एक और भी कठोर धारणा, जिसे एक्सपोनेंशियल टाइम परिकल्पना (SETH) के रूप में जाना जाता है, यह अनुमान लगाती है कि बूलियन संतुष्टि समस्या |<math>k</math>-सैट की आवश्यकता है <math>2^{(1-\varepsilon_k)n}</math> समय, जहाँ <math>\lim_{k \rightarrow \infty} \varepsilon_k = 0</math>.
+  | year = 1999}}</ref> एक और भी कठोर धारणा, जिसे एक्सपोनेंशियल टाइम परिकल्पना (एसईटीएच) के रूप में जाना जाता है, यह अनुमान लगाती है कि <math>k</math>-सैट को <math>2^{(1-\varepsilon_k)n}</math>समय की आवश्यकता होती है, जहाँ <math>\lim_{k \rightarrow \infty} \varepsilon_k = 0</math> है। ईटीएच, एसईटीएच, और संबंधित कम्प्यूटेशनल कठोरता धारणाएं सूक्ष्म जटिलता परिणामों को कम करने की अनुमति देती हैं, उदाहरण; परिणाम जो बहुपद समय और अर्ध-बहुपद समय में अंतर करते हैं,<ref name=BKW15 /> या यहाँ तक कि  <math>n^{1.99}</math> और <math>n^2</math> [[पैरामीट्रिज्ड जटिलता]] में ऐसी धारणाएं भी उपयोगी होती हैं।<ref>{{cite conference
-ईटीएच, एसईटीएच, और संबंधित कम्प्यूटेशनल कठोरता धारणाएं सूक्ष्म जटिलता परिणामों को कम करने की अनुमति देती हैं, उदा। परिणाम जो बहुपद समय और समय जटिलता को अलग करते हैं#अर्ध-बहुपद समय|अर्ध-बहुपद समय,<ref name=BKW15 />या और भी <math>n^{1.99}</math> बनाम <math>n^2</math>.<ref>{{cite conference
   | last1 = Abboud | first1 = Amir
   | last2 = Vassilevska-Williams | first2 = Virginia |author2-link = Virginia Vassilevska Williams
@@ Line 168: / Line 167: @@
   | pages = 39–51
   | title = Automata, Languages, and Programming - 41st International Colloquium, ICALP 2014
-  | year = 2014}}</ref>
+  | year = 2014}}</ref><ref name = LMS11>
-[[पैरामीट्रिज्ड जटिलता]] में ऐसी धारणाएं भी उपयोगी होती हैं।<ref name = LMS11>
 {{cite journal
   | last1 = Lokshtanov | first1 = Daniel
@@ Line 183: / Line 181: @@
-=== औसत-मामला कठोरता धारणा ===
+=== औसत-स्थिति कठोरता धारणा ===
 {{Main|औसत-स्थिति की जटिलता}}
-कुछ कम्प्यूटेशनल समस्याओं को उदाहरणों के एक विशेष वितरण पर औसतन कठिन माना जाता है।
+कुछ कम्प्यूटेशनल समस्याओं को उदाहरणों के एक विशेष वितरण पर औसतन कठिन माना जाता है। उदाहरण के लिए, प्लांटेड क्लिक समस्या में, इनपुट एक यादृच्छिक ग्राफ नमूना है, एक एर्डोस-रेनी रैंडम ग्राफ का नमूना लेकर और फिर एक यादृच्छिक <math>k</math>-क्लिक "रोपण", अर्थात् <math>k</math>  के समान रूप से यादृच्छिक नोड्स को जोड़ना (जहाँ <math>2\log_2 n \ll k \ll \sqrt n</math>) और लक्ष्य प्लांटेड <math>k</math>- क्लिक (जो अद्वितीय डब्ल्यू.एच.पी. है) को खोजना है।<ref name="ab">{{cite book|title=Computational Complexity: A Modern Approach|first1=Sanjeev|last1=Arora|author1-link=Sanjeev Arora|first2=Boaz|last2=Barak|publisher=Cambridge University Press|year=2009|isbn=9780521424264|pages=362–363|url=https://books.google.com/books?id=8Wjqvsoo48MC&pg=PA362}}.</ref> एक अन्य महत्वपूर्ण उदाहरण उरीएल फीगे की परिकल्पना है, जो 3-एसएटी के यादृच्छिक उदाहरणों के बारे में एक कम्प्यूटेशनल कठोरता धारणा है (चरों के खंड के एक विशिष्ट अनुपात को बनाए रखने के लिए नमूना)।<ref name = Feige02>
-उदाहरण के लिए, प्लांटेड क्लिक समस्या में, इनपुट एक यादृच्छिक ग्राफ नमूना है, एक एर्दोस-रेनी मॉडल का नमूना लेकर | एर्डोस-रेनी यादृच्छिक ग्राफ और फिर एक यादृच्छिक रोपण <math>k</math>-क्लिक, यानी कनेक्ट करना <math>k</math> समान रूप से यादृच्छिक नोड्स (जहाँ <math>2\log_2 n \ll k \ll \sqrt n</math>), और लक्ष्य लगाए गए को ढूंढना है <math>k</math>-क्लिक (जो अद्वितीय w.h.p. है)।<ref name="ab">{{cite book|title=Computational Complexity: A Modern Approach|first1=Sanjeev|last1=Arora|author1-link=Sanjeev Arora|first2=Boaz|last2=Barak|publisher=Cambridge University Press|year=2009|isbn=9780521424264|pages=362–363|url=https://books.google.com/books?id=8Wjqvsoo48MC&pg=PA362}}.</ref>
-एक अन्य महत्वपूर्ण उदाहरण उरीएल फीगे की परिकल्पना है, जो बूलियन संतुष्टि समस्या के यादृच्छिक उदाहरणों के बारे में एक कम्प्यूटेशनल कठोरता धारणा है | 3-एसएटी (चर के खंड के विशिष्ट अनुपात को बनाए रखने के लिए नमूना)।<ref name = Feige02>
 {{cite conference
 | last1 = Feige | first1 = Uriel |author1-link = Uriel Feige
@@ Line 195: / Line 191: @@
   | title = Proceedings on 34th Annual ACM Symposium on Theory of Computing (STOC)
   | year = 2002
-}}</ref>
+}}</ref> औसत-स्थिति कम्प्यूटेशनल कठोरता धारणाएँ आँकड़ों जैसे अनुप्रयोगों में औसत-स्थिति कठोरता को प्रमाणित करने के लिए उपयोगी होती हैं, जहाँ इनपुट पर प्राकृतिक वितरण होता है।<ref name = BR13>
-औसत-स्थिति कम्प्यूटेशनल कठोरता धारणाएँ आँकड़ों जैसे अनुप्रयोगों में औसत-स्थिति कठोरता को प्रमाणित करने के लिए उपयोगी होती हैं, जहाँ इनपुट पर प्राकृतिक वितरण होता है।<ref name = BR13>
 {{cite conference
 | last1 = Berthet | first1 = Quentin
@@ Line 205: / Line 200: @@
   | url = http://jmlr.org/proceedings/papers/v30/Berthet13.html
   | year = 2013
-}}</ref>
+}}</ref> इसके अतिरिक्त, प्लांटेड क्लिक कठोरता धारणा का उपयोग अन्य समस्याओं के बहुपद और अर्ध-बहुपद सबसे खराब समय जटिलता के बीच अंतर करने के लिए भी किया गया है,<ref name = HK11>{{cite journal
-इसके अतिरिक्त, प्लांटेड क्लिक हार्डनेस धारणा का उपयोग अन्य समस्याओं के बहुपद और अर्ध-बहुपद वर्स्ट-स्थिति टाइम जटिलता के बीच अंतर करने के लिए भी किया गया है,<ref name = HK11>{{cite journal
   | last1 = Hazan | first1 = Elad
   | last2 = Krauthgamer | first2 = Robert
@@ Line 216: / Line 210: @@
   | number = 1
   | year = 2011| citeseerx = 10.1.1.139.7326
-  }}</ref>
+  }}</ref> इसी तरह घातीय समय परिकल्पना के लिए भी किया गया है।
-इसी तरह #Exponential Time Hypothesis (ETH) और वेरिएंट।
+=== अद्वितीय खेल ===
+{{Main|अद्वितीय खेल अनुमान}}
-=== अनोखा खेल ===
+अद्वितीय लेबल कवर समस्या एक बाधा संतुष्टि समस्या है, जहां प्रत्येक बाधा <math>C</math> में दो चर <math>x,y</math> सम्मिलित हैं, और <math>x</math> के प्रत्येक मान के लिए <math>y</math> अद्वितीय मान है जो <math>C</math> को संतुष्ट करता है। यह निर्धारित करना कि क्या सभी बाधाओं को पूरा किया जा सकता है, आसान है, लेकिन अद्वितीय खेल कंजेक्चर (यूजीसी) का मानना है कि यह निर्धारित करना कि क्या लगभग सभी बाधाएं (<math>(1-\varepsilon)</math>-अंश, किसी भी स्थिरांक के लिए <math>\varepsilon>0</math>) संतुष्ट हो सकते हैं या उनमें से कोई नहीं (<math>\varepsilon</math>-अंश) भी संतुष्ट किया जा सकता है, वे एनपी-कठोर है।<ref name=khot10 /> सन्निकटन समस्याओं को अक्सर यूजीसी मानते हुए एनपी-कठोर के रूप में जाना जाता है; ऐसी समस्याओं को यूजी-कठोर कहा जाता है। विशेष रूप से, यह मानते हुए कि यूजीसी में एक अर्ध-निश्चित प्रोग्रामिंग एल्गोरिथम है जो कई महत्वपूर्ण समस्याओं के लिए इष्टतम सन्निकटन गारंटी प्राप्त करता है।<ref name = rag08>
-{{Main|अनोखा खेल अनुमान}}
-अनोखा खेल अनुमान #अद्वितीय लेबल कवर समस्या एक बाधा संतुष्टि समस्या है, जहां प्रत्येक बाधा <math>C</math> दो चर सम्मिलित हैं <math>x,y</math>, और के प्रत्येक मूल्य के लिए <math>x</math> का एक अनूठा मूल्य है <math>y</math> जो संतुष्ट करता है <math>C</math>.
-यह निर्धारित करना कि क्या सभी बाधाओं को पूरा किया जा सकता है, आसान है, लेकिन यूनीक गेम कंजेक्चर (यूजीसी) का मानना है कि यह निर्धारित करना कि क्या लगभग सभी बाधाएं (<math>(1-\varepsilon)</math>-अंश, किसी भी स्थिरांक के लिए <math>\varepsilon>0</math>) संतुष्ट हो सकते हैं या उनमें से लगभग कोई नहीं (<math>\varepsilon</math>-अंश) संतुष्ट किया जा सकता है एनपी-हार्ड है।<ref name=khot10 />सन्निकटन समस्याओं को अधिकांशतः यूजीसी मानते हुए एनपी-हार्ड के रूप में जाना जाता है; ऐसी समस्याओं को यूजी-हार्ड कहा जाता है।
-विशेष रूप से, यह मानते हुए कि UGC में एक अर्ध-निश्चित प्रोग्रामिंग एल्गोरिथम है जो कई महत्वपूर्ण समस्याओं के लिए इष्टतम सन्निकटन गारंटी प्राप्त करता है।<ref name = rag08>
 {{cite conference
   | first = Prasad |last=Raghavendra
@@ Line 233: / Line 225: @@
-====छोटा सेट विस्तार====
+====लघु सेट विस्तार====
-{{main|छोटा सेट विस्तार परिकल्पना}}
+{{main|लघु सेट विस्तार परिकल्पना}}
-यूनिक लेबल कवर समस्या से निकटता से संबंधित है स्मॉल सेट एक्सपेंशन (एसएसई) समस्या: एक ग्राफ दिया गया <math>G = (V,E)</math>, वर्टिकल का एक छोटा सेट खोजें (आकार का <math>n/\log(n)</math>) जिसका विस्तारक ग्राफ#एज विस्तार न्यूनतम है।
-यह ज्ञात है कि यदि एसएसई का अनुमान लगाना कठिन है, तो अद्वितीय लेबल कवर भी ऐसा ही है। इसलिए, स्मॉल सेट एक्सपेंशन परिकल्पना, जो मानती है कि एसएसई का अनुमान लगाना कठिन है, अद्वितीय गेम अनुमान की तुलना में एक कठोर (लेकिन निकटता से संबंधित) धारणा है।<ref name="rs10">
+यूनिक लेबल कवर समस्या से निकटता से संबंधित है, लघु सेट विस्तार (एसएसई) समस्या: एक ग्राफ <math>G = (V,E)</math> दिया गया, वर्टिकल का एक लघु सेट (<math>n/\log(n)</math> आकार का) खोजें; जिसका एज विस्तार न्यूनतम है। यह ज्ञात है कि यदि एसएसई का अनुमान लगाना कठिन है, तो अद्वितीय लेबल कवर भी ऐसा ही है। इसलिए, लघु सेट विस्तार परिकल्पना, जो मानती है कि एसएसई का अनुमान लगाना कठिन है, अद्वितीय खेल अनुमान की तुलना में एक कठोर (लेकिन निकटता से संबंधित) धारणा है।<ref name="rs10">
 {{cite conference
   | first1 = Prasad |last1=Raghavendra
@@ Line 246: / Line 236: @@
   | pages = 755–764
   | title = 42nd Annual ACM Symposium on theory of Computing (STOC) 2010
-  | year = 2010}}</ref>
+  | year = 2010}}</ref> कुछ सन्निकटन समस्याओं को एसएसई-कठोर के रूप में जाना जाता है<ref>{{cite journal
-कुछ सन्निकटन समस्याओं को एसएसई-हार्ड के रूप में जाना जाता है<ref>{{cite journal
   | first1 = Yu |last1=Wu
   | first2 = Per |last2=Austrin
@@ Line 258: / Line 247: @@
   | volume = 49
   | year = 2014| doi-access = free
-  }}</ref> (अर्थात कम से कम उतना ही मुश्किल जितना अनुमानित एसएसई)।
+  }}</ref> (अर्थात कम से कम उतना ही जटिल जितना अनुमानित एसएसई)।
 === 3एसयूएम अनुमान ===
 {{Main|3एसयूएम}}
-का एक सेट दिया <math>n</math> संख्याएँ, 3एसयूएम समस्या पूछती है कि क्या संख्याओं का एक त्रिक है जिसका योग शून्य है।
+<math>n</math> संख्याओं के एक सेट को देखते हुए, 3एसयूएम समस्या पूछती है कि क्या संख्याओं का एक त्रिक है जिसका योग शून्य है। 3एसयूएम के लिए एक द्विघात-समय एल्गोरिथ्म है, और यह अनुमान लगाया गया है कि कोई भी एल्गोरिथ्म 3एसयूएम को "वास्तव में उप-द्विघात समय" में हल नहीं कर सकता है: 3एसयूएम अनुमान कम्प्यूटेशनल कठोरता धारणा है कि 3एसयूएम के लिए कोई <math>O(n^{2-\varepsilon})</math> समय एल्गोरिदम नहीं हैं (किसी भी स्थिरांक के लिए <math>\varepsilon > 0</math>)। यह अनुमान कई समस्याओं के लिए निकट-द्विघात निचली सीमा को प्रमाणित करने के लिए उपयोगी है, अधिकतर [[कम्प्यूटेशनल ज्यामिति]] से उपयोगी है।<ref>
-एसयूएम के लिए एक द्विघात-समय एल्गोरिथ्म है, और यह अनुमान लगाया गया है कि कोई भी एल्गोरिथ्म वास्तव में उप-द्विघात समय में 3एसयूएम को हल नहीं कर सकता है:
-एसयूएम अनुमान कम्प्यूटेशनल कठोरता धारणा है कि नहीं हैं <math>O(n^{2-\varepsilon})</math>3एसयूएम के लिए समय एल्गोरिदम (किसी भी स्थिरांक के लिए <math>\varepsilon > 0</math>).
-यह अनुमान कई समस्याओं के लिए निकट-द्विघात निचली सीमा को प्रमाणित करने के लिए उपयोगी है, अधिकतर [[कम्प्यूटेशनल ज्यामिति]] से।<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 00:51, 22 May 2023

Contents

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

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

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

मिथ्याकरण

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

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

आरएसए समस्या

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

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

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

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

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

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

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

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

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

अद्वितीय खेल

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

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

यह भी देखें

संदर्भ

Navigation

Navigation

Wiki tools

Wiki tools

Anonymous

Search

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

Revision as of 00:51, 22 May 2023

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

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

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

मिथ्याकरण

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

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

आरएसए समस्या

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

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

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

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

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

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

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

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

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

अद्वितीय खेल

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

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

यह भी देखें

संदर्भ

Navigation

Wiki tools

Page tools

Other projects

Categories