3 सम: Difference between revisions

Revision as of 16:50, 17 July 2023

Unsolved problem in computer science:

Is there an algorithm to solve the 3SUM problem in time $O(n^{2-\epsilon })$ , for some $\epsilon >0$ ?

(more unsolved problems in computer science)

कम्प्यूटेशनल जटिलता सिद्धांत में, 3SUM समस्या पूछती है कि क्या दिया गया सेट $n$ वास्तविक संख्याओं में तीन तत्व होते हैं जिनका योग शून्य होता है। सामान्यीकृत संस्करण, k-SUM, k संख्याओं पर समान प्रश्न पूछता है। 3SUM को आसानी से हल किया जा सकता है $O(n^{2})$ समय, और मिलान $\Omega (n^{\lceil k/2\rceil })$ गणना के कुछ विशेष मॉडलों में निचली सीमाएं ज्ञात होती हैं (Erickson 1999).

यह अनुमान लगाया गया था कि 3SUM के लिए किसी भी नियतात्मक एल्गोरिदम की आवश्यकता होती है $\Omega (n^{2})$ समय। 2014 में, मूल 3SUM अनुमान का एलन ग्रोनलुंड और सेठ पेटी ने खंडन किया था, जिन्होंने नियतात्मक एल्गोरिदम दिया था जो 3SUM को हल करता है $O(n^{2}/({\log n}/{\log \log n})^{2/3})$ समय।^[1] इसके अतिरिक्त, ग्रोनलुंड और पेटी ने दिखाया कि 3SUM की 4-निर्णय वृक्ष मॉडल#रैखिक निर्णय वृक्ष जटिलता है $O(n^{3/2}{\sqrt {\log n}})$ . बाद में इन सीमाओं में सुधार किया गया।^[2]^[3]^[4] 3SUM के लिए वर्तमान सबसे प्रसिद्ध एल्गोरिदम चलता है $upper O left parenthesis n squared left parenthesis log log n right parenthesis Superscript upper O left parenthesis 1 right parenthesis Baseline divided by log squared n right parenthesis$

[1]

[2]

[3]

[4]

@@ Line 3: / Line 3: @@
 {{unsolved|computer science|Is there an algorithm to solve the 3SUM problem in time  <math>O(n^{2-\epsilon})</math>, for some <math>\epsilon>0</math>?}}
-[[कम्प्यूटेशनल जटिलता सिद्धांत]] में, 3SUM समस्या पूछती है कि क्या दिया गया सेट <math>n</math> वास्तविक संख्याओं में तीन तत्व होते हैं जिनका योग शून्य होता है। एक सामान्यीकृत संस्करण, k-SUM, k संख्याओं पर समान प्रश्न पूछता है। 3SUM को आसानी से हल किया जा सकता है <math>O(n^2)</math> समय, और मिलान <math>\Omega(n^{\lceil k/2 \rceil})</math> गणना के कुछ विशेष मॉडलों में निचली सीमाएं ज्ञात होती हैं {{harv|Erickson|1999}}.
+[[कम्प्यूटेशनल जटिलता सिद्धांत]] में, 3SUM समस्या पूछती है कि क्या दिया गया सेट <math>n</math> वास्तविक संख्याओं में तीन तत्व होते हैं जिनका योग शून्य होता है। सामान्यीकृत संस्करण, k-SUM, k संख्याओं पर समान प्रश्न पूछता है। 3SUM को आसानी से हल किया जा सकता है <math>O(n^2)</math> समय, और मिलान <math>\Omega(n^{\lceil k/2 \rceil})</math> गणना के कुछ विशेष मॉडलों में निचली सीमाएं ज्ञात होती हैं {{harv|Erickson|1999}}.
 यह अनुमान लगाया गया था कि 3SUM के लिए किसी भी नियतात्मक एल्गोरिदम की आवश्यकता होती है <math> \Omega(n^2) </math> समय।
-में, मूल 3SUM अनुमान का एलन ग्रोनलुंड और सेठ पेटी ने खंडन किया था, जिन्होंने एक नियतात्मक एल्गोरिदम दिया था जो 3SUM को हल करता है <math>O(n^2 / ({\log n} / {\log \log n})^{2/3})</math> समय।{{sfn|Grønlund|Pettie|2014}}
+में, मूल 3SUM अनुमान का एलन ग्रोनलुंड और सेठ पेटी ने खंडन किया था, जिन्होंने नियतात्मक एल्गोरिदम दिया था जो 3SUM को हल करता है <math>O(n^2 / ({\log n} / {\log \log n})^{2/3})</math> समय।{{sfn|Grønlund|Pettie|2014}}
 इसके अतिरिक्त, ग्रोनलुंड और पेटी ने दिखाया कि 3SUM की 4-निर्णय वृक्ष मॉडल#रैखिक निर्णय वृक्ष जटिलता है <math> O(n^{3/2}\sqrt{\log n}) </math>.
 बाद में इन सीमाओं में सुधार किया गया।{{sfn|Freund|2017}}{{sfn|Gold|Sharir|2017}}{{sfn|Chan|2018}}
@@ Line 13: / Line 13: @@
 यह अभी भी अनुमान लगाया गया है कि 3SUM का समाधान नहीं हो सका है <math>O(n^{2-\Omega(1)})</math> अपेक्षित समय।<ref name=kpp14/>
-जब श्रेणी में तत्व पूर्णांक हों <math>[-N, \dots, N]</math>, 3SUM में हल किया जा सकता है <math>O(n + N\log N)</math> इनपुट सेट का प्रतिनिधित्व करके समय <math>S</math> [[बिट सरणी]] के रूप में, सेट की गणना करना <math>S+S</math> तेज फूरियर रूपांतरण का उपयोग करते हुए एक [[असतत कनवल्शन]] के रूप में सभी जोड़ीवार योगों की, और अंत में इस सेट की तुलना की गई <math>S</math>.<ref>{{Introduction to Algorithms|edition=3}} Ex. 30.1–7, p.&nbsp;906.</ref>
+जब श्रेणी में तत्व पूर्णांक हों <math>[-N, \dots, N]</math>, 3SUM में हल किया जा सकता है <math>O(n + N\log N)</math> इनपुट सेट का प्रतिनिधित्व करके समय <math>S</math> [[बिट सरणी]] के रूप में, सेट की गणना करना <math>S+S</math> तेज फूरियर रूपांतरण का उपयोग करते हुए [[असतत कनवल्शन]] के रूप में सभी जोड़ीवार योगों की, और अंत में इस सेट की तुलना की गई <math>S</math>.<ref>{{Introduction to Algorithms|edition=3}} Ex. 30.1–7, p.&nbsp;906.</ref>
 == द्विघात एल्गोरिथ्म ==
-मान लीजिए कि इनपुट ऐरे है <math>S[0..n-1]</math>. कंप्यूटिंग के पूर्णांक (शब्द रैम) मॉडल में, 3SUM को हल किया जा सकता है <math>O(n^2)</math> प्रत्येक संख्या डालने पर औसतन समय <math>S[i]</math> एक [[हैश तालिका]] में, और फिर, प्रत्येक सूचकांक के लिए <math>i</math> और <math>j</math>, जाँच कर रहा है कि हैश तालिका में पूर्णांक है या नहीं <math>-(S[i]+S[j])</math>.
+मान लीजिए कि इनपुट ऐरे है <math>S[0..n-1]</math>. कंप्यूटिंग के पूर्णांक (शब्द रैम) मॉडल में, 3SUM को हल किया जा सकता है <math>O(n^2)</math> प्रत्येक संख्या डालने पर औसतन समय <math>S[i]</math> [[हैश तालिका]] में, और फिर, प्रत्येक सूचकांक के लिए <math>i</math> और <math>j</math>, जाँच कर रहा है कि हैश तालिका में पूर्णांक है या नहीं <math>-(S[i]+S[j])</math>.
-कंप्यूटिंग या वास्तविक रैम के [[तुलना (कंप्यूटर प्रोग्रामिंग)]]-आधारित मॉडल में एक ही समय में समस्या को हल करना भी संभव है, जिसके लिए हैशिंग की अनुमति नहीं है। नीचे दिया गया एल्गोरिदम पहले इनपुट ऐरे को सॉर्ट करता है और फिर सावधानीपूर्वक सभी संभावित जोड़ियों का परीक्षण करता है, जिससे क्रमबद्ध सूची में जोड़ियों के लिए बाइनरी खोज की आवश्यकता से बचा जा सकता है, जिससे सबसे खराब स्थिति प्राप्त होती है। <math>O(n^2)</math> समय, इस प्रकार है.<ref>[http://www.ti.inf.ethz.ch/ew/courses/CG09/materials/v12.pdf Visibility Graphs and 3-Sum] by Michael Hoffmann</ref>
+कंप्यूटिंग या वास्तविक रैम के [[तुलना (कंप्यूटर प्रोग्रामिंग)]]-आधारित मॉडल में ही समय में समस्या को हल करना भी संभव है, जिसके लिए हैशिंग की अनुमति नहीं है। नीचे दिया गया एल्गोरिदम पहले इनपुट ऐरे को सॉर्ट करता है और फिर सावधानीपूर्वक सभी संभावित जोड़ियों का परीक्षण करता है, जिससे क्रमबद्ध सूची में जोड़ियों के लिए बाइनरी खोज की आवश्यकता से बचा जा सकता है, जिससे सबसे खराब स्थिति प्राप्त होती है। <math>O(n^2)</math> समय, इस प्रकार है.<ref>[http://www.ti.inf.ethz.ch/ew/courses/CG09/materials/v12.pdf Visibility Graphs and 3-Sum] by Michael Hoffmann</ref>
 सॉर्ट(एस);
   i = 0 से n - 2 के लिए करें
-     ए = एस[आई];
+  ए = एस[आई];
-     प्रारंभ = मैं + 1;
+  प्रारंभ = मैं + 1;
-     अंत = एन - 1;
+  अंत = एन - 1;
-     जबकि (प्रारंभ <अंत) करते हैं
+  जबकि (प्रारंभ <अंत) करते हैं
-         बी = एस[प्रारंभ]
+  बी = एस[प्रारंभ]
-         सी = एस[अंत];
+  सी = एस[अंत];
-         यदि (ए + बी + सी == 0) तो
+  यदि (ए + बी + सी == 0) तो
-             आउटपुट ए, बी, सी;
+  आउटपुट ए, बी, सी;
-             // शून्य के योग वाले सभी त्रिक संयोजनों की खोज जारी रखें।
+  // शून्य के योग वाले सभी त्रिक संयोजनों की खोज जारी रखें।
-             // हमें अंत और प्रारंभ दोनों को एक साथ अपडेट करने की आवश्यकता है क्योंकि सरणी मान अलग-अलग हैं।
+  // हमें अंत और प्रारंभ दोनों को साथ अपडेट करने की आवश्यकता है क्योंकि सरणी मान अलग-अलग हैं।
-             प्रारंभ = प्रारंभ + 1;
+  प्रारंभ = प्रारंभ + 1;
-             अंत = अंत - 1;
+  अंत = अंत - 1;
-         अन्यथा यदि (ए + बी + सी > 0) तो
+  अन्यथा यदि (ए + बी + सी > 0) तो
-             अंत = अंत - 1;
+  अंत = अंत - 1;
-         अन्य
+  अन्य
-             प्रारंभ = प्रारंभ + 1;
+  प्रारंभ = प्रारंभ + 1;
-     अंत
+  अंत
   अंत
-निम्नलिखित उदाहरण एक छोटे क्रमबद्ध सरणी पर इस एल्गोरिदम के निष्पादन को दिखाता है। ए के वर्तमान मान लाल रंग में दिखाए गए हैं, बी और सी के मान मैजेंटा में दिखाए गए हैं।
+निम्नलिखित उदाहरण छोटे क्रमबद्ध सरणी पर इस एल्गोरिदम के निष्पादन को दिखाता है। ए के वर्तमान मान लाल रंग में दिखाए गए हैं, बी और सी के मान मैजेंटा में दिखाए गए हैं।
    <span style= color:red >-25</span> <span style= color:magenta >-10</span> -7 -3 2 4 8 <span style= color:magenta >10</span> (a +बी+सी==-25)
    <span style= color:red >-25</span> -10 <span style= color:magenta >-7</span> -3 2 4 8 <span style= color:magenta >10</span> (ए +बी+सी==-22)
@@ Line 51: / Line 51: @@
    -25 <span style= color:red >-10</span> -7 -3 <span style= color:magenta >2</span> 4 <span style= color:magenta >8</span> 10 (a +बी+सी==0)
-एल्गोरिथम की शुद्धता इस प्रकार देखी जा सकती है। मान लीजिए कि हमारे पास एक समाधान है a + b + c = 0. चूंकि सूचक केवल एक ही दिशा में चलते हैं, हम एल्गोरिदम को तब तक चला सकते हैं जब तक कि सबसे बाईं ओर का सूचक a की ओर इंगित न कर दे। एल्गोरिथम को तब तक चलाएँ जब तक कि शेष संकेतकों में से कोई एक b या c, जो भी पहले हो, को इंगित न कर दे। तब एल्गोरिथ्म तब तक चलेगा जब तक अंतिम सूचक सकारात्मक समाधान देते हुए शेष पद की ओर इशारा नहीं करता।
+एल्गोरिथम की शुद्धता इस प्रकार देखी जा सकती है। मान लीजिए कि हमारे पास समाधान है a + b + c = 0. चूंकि सूचक केवल ही दिशा में चलते हैं, हम एल्गोरिदम को तब तक चला सकते हैं जब तक कि सबसे बाईं ओर का सूचक a की ओर इंगित न कर दे। एल्गोरिथम को तब तक चलाएँ जब तक कि शेष संकेतकों में से कोई b या c, जो भी पहले हो, को इंगित न कर दे। तब एल्गोरिथ्म तब तक चलेगा जब तक अंतिम सूचक सकारात्मक समाधान देते हुए शेष पद की ओर इशारा नहीं करता।
 == वेरिएंट ==
@@ Line 67: / Line 67: @@
 एक ही सारणी में 3 संख्याओं को खोजने के बजाय, हम उन्हें 3 अलग-अलग सारणियों में खोज सकते हैं। यानी, तीन सरणियाँ X, Y और Z दी गई हैं, तीन संख्याएँ खोजें {{math|''a''∈''X'', ''b''∈''Y'', ''c''∈''Z''}}, ऐसा है कि {{tmath|a+b+c{{=}}0}}. 1-सरणी वैरिएंट 3SUM×1 और 3-सरणी वैरिएंट 3SUM×3 को कॉल करें।
-SUM×1 के लिए एक सॉल्वर दिए जाने पर, 3SUM×3 समस्या को निम्नलिखित तरीके से हल किया जा सकता है (यह मानते हुए कि सभी तत्व पूर्णांक हैं):
+SUM×1 के लिए सॉल्वर दिए जाने पर, 3SUM×3 समस्या को निम्नलिखित तरीके से हल किया जा सकता है (यह मानते हुए कि सभी तत्व पूर्णांक हैं):
 * X, Y और Z में प्रत्येक तत्व के लिए, सेट करें: {{tmath|X[i] \gets X[i]*10+1}}, {{tmath|Y[i] \gets Y[i]*10+2}}, {{tmath|Z[i] \gets Z[i]*10-3}}.
-* मान लीजिए S, सारणियों X, Y और Z का एक संयोजन है।
+* मान लीजिए S, सारणियों X, Y और Z का संयोजन है।
 * तीन तत्वों को खोजने के लिए 3SUM×1 ओरेकल का उपयोग करें {{tmath|a' \in S,\ b' \in S,\ c' \in S}} ऐसा है कि {{tmath|a'+b'+c'{{=}}0}}.
 * वापस करना {{tmath|a \gets (a'-1)/10,\ b \gets (b'-2)/10,\ c \gets (c'+3)/10}}.
@@ Line 83: / Line 83: @@
 ==== Conv3SUM से 3SUM तक कमी ====
-SUM के लिए एक सॉल्वर दिए जाने पर, Conv3SUM समस्या को निम्नलिखित तरीके से हल किया जा सकता है।<ref name=patrascu10/>* एक नई सरणी टी परिभाषित करें, जैसे कि प्रत्येक सूचकांक के लिए: <math>T[i]=2n S[i]+i</math> (जहाँ n सरणी में तत्वों की संख्या है, और सूचकांक 0 से n-1 तक चलते हैं)।
+SUM के लिए सॉल्वर दिए जाने पर, Conv3SUM समस्या को निम्नलिखित तरीके से हल किया जा सकता है।<ref name=patrascu10/>* नई सरणी टी परिभाषित करें, जैसे कि प्रत्येक सूचकांक के लिए: <math>T[i]=2n S[i]+i</math> (जहाँ n सरणी में तत्वों की संख्या है, और सूचकांक 0 से n-1 तक चलते हैं)।
 * सरणी T पर 3SUM हल करें।
 शुद्धता प्रमाण:
 * यदि मूल सारणी में त्रिगुण है <math>S[i+j]=S[i]+S[j]</math>, तब <math>T[i+j]=2n S[i+j]+i+j = (2n S[i] + i) + (2n S[j] + j)=T[i]+T[j]</math>, इसलिए यह समाधान 3SUM द्वारा T पर पाया जाएगा।
-* इसके विपरीत, यदि नए ऐरे में ट्रिपल विथ है <math>T[k]=T[i]+T[j]</math>, तब <math>2n S[k] + k = 2n(S[i]+S[j]) + (i+j)</math>. क्योंकि <math>i+j<2n</math>, अनिवार्य रूप से <math>S[k] = S[i]+S[j]</math> और <math>k=i+j</math>, इसलिए यह S पर Conv3SUM के लिए एक वैध समाधान है।
+* इसके विपरीत, यदि नए ऐरे में ट्रिपल विथ है <math>T[k]=T[i]+T[j]</math>, तब <math>2n S[k] + k = 2n(S[i]+S[j]) + (i+j)</math>. क्योंकि <math>i+j<2n</math>, अनिवार्य रूप से <math>S[k] = S[i]+S[j]</math> और <math>k=i+j</math>, इसलिए यह S पर Conv3SUM के लिए वैध समाधान है।
 ==== 3SUM से Conv3SUM तक कमी ====
-Conv3SUM के लिए एक सॉल्वर दिए जाने पर, 3SUM समस्या को निम्नलिखित तरीके से हल किया जा सकता है।<ref name=kpp14>{{Cite arXiv|eprint=1407.6756|last1=Kopelowitz|first1=Tsvi|title=3SUM Hardness in (Dynamic) Data Structures|last2=Pettie|first2=Seth|last3=Porat|first3=Ely|class=cs.DS|year=2014}}</ref><ref name=patrascu10/>
+Conv3SUM के लिए सॉल्वर दिए जाने पर, 3SUM समस्या को निम्नलिखित तरीके से हल किया जा सकता है।<ref name=kpp14>{{Cite arXiv|eprint=1407.6756|last1=Kopelowitz|first1=Tsvi|title=3SUM Hardness in (Dynamic) Data Structures|last2=Pettie|first2=Seth|last3=Porat|first3=Ely|class=cs.DS|year=2014}}</ref><ref name=patrascu10/>
-कमी एक [[हैश फंकशन]] का उपयोग करती है। पहले सन्निकटन के रूप में, मान लें कि हमारे पास एक रैखिक हैश फ़ंक्शन है, यानी एक फ़ंक्शन h ऐसा है कि:
+कमी [[हैश फंकशन]] का उपयोग करती है। पहले सन्निकटन के रूप में, मान लें कि हमारे पास रैखिक हैश फ़ंक्शन है, यानी फ़ंक्शन h ऐसा है कि:
 :<math>h(x+y)=h(x)+h(y)</math>
-मान लीजिए कि सभी तत्व श्रेणी में पूर्णांक हैं: 0...N-1, और फ़ंक्शन h प्रत्येक तत्व को सूचकांकों की छोटी श्रेणी में एक तत्व में मैप करता है: 0...n-1। एक नया ऐरे टी बनाएं और एस के प्रत्येक तत्व को टी में उसके हैश मान पर भेजें, यानी, एस में प्रत्येक एक्स के लिए({{tmath|\forall x \in S}}):
+मान लीजिए कि सभी तत्व श्रेणी में पूर्णांक हैं: 0...N-1, और फ़ंक्शन h प्रत्येक तत्व को सूचकांकों की छोटी श्रेणी में तत्व में मैप करता है: 0...n-1। नया ऐरे टी बनाएं और एस के प्रत्येक तत्व को टी में उसके हैश मान पर भेजें, यानी, एस में प्रत्येक एक्स के लिए({{tmath|\forall x \in S}}):
 :<math>T[h(x)] = x</math>
-प्रारंभ में, मान लें कि मैपिंग अद्वितीय हैं (अर्थात टी में प्रत्येक कोशिका एस से केवल एक ही तत्व स्वीकार करती है)। T पर Conv3SUM को हल करें। अभी:
+प्रारंभ में, मान लें कि मैपिंग अद्वितीय हैं (अर्थात टी में प्रत्येक कोशिका एस से केवल ही तत्व स्वीकार करती है)। T पर Conv3SUM को हल करें। अभी:
 * यदि 3SUM के लिए कोई समाधान है: <math>z=x+y</math>, तब: <math>T[h(z)]=T[h(x)]+T[h(y)]</math> और <math>h(z)=h(x)+h(y)</math>, इसलिए यह समाधान T पर Conv3SUM सॉल्वर द्वारा पाया जाएगा।
 * इसके विपरीत, यदि T पर Conv3SUM पाया जाता है, तो जाहिर तौर पर यह S पर 3SUM समाधान से मेल खाता है क्योंकि T केवल S का क्रमपरिवर्तन है।
-यह आदर्श समाधान काम नहीं करता है, क्योंकि कोई भी हैश फ़ंक्शन S के कई अलग-अलग तत्वों को T के एक ही सेल में मैप कर सकता है। चाल एक सरणी बनाने की है {{tmath|T^*}} T के प्रत्येक सेल से एक यादृच्छिक तत्व का चयन करके, और Conv3SUM को चालू करें {{tmath|T^*}}. यदि कोई समाधान मिल जाता है, तो यह S पर 3SUM के लिए एक सही समाधान है। यदि कोई समाधान नहीं मिलता है, तो एक अलग यादृच्छिक बनाएं {{tmath|T^*}} और फिर प्रयत्न करें। मान लीजिए कि टी के प्रत्येक सेल में अधिकतम आर तत्व हैं। फिर समाधान खोजने की संभावना (यदि कोई समाधान मौजूद है) यह संभावना है कि यादृच्छिक चयन प्रत्येक सेल से सही तत्व का चयन करेगा, जो है <math>(1/R)^3</math>. Conv3SUM चलाकर <math>R^3</math> कई बार, उच्च संभावना के साथ समाधान मिल जाएगा।
+यह आदर्श समाधान काम नहीं करता है, क्योंकि कोई भी हैश फ़ंक्शन S के कई अलग-अलग तत्वों को T के ही सेल में मैप कर सकता है। चाल सरणी बनाने की है {{tmath|T^*}} T के प्रत्येक सेल से यादृच्छिक तत्व का चयन करके, और Conv3SUM को चालू करें {{tmath|T^*}}. यदि कोई समाधान मिल जाता है, तो यह S पर 3SUM के लिए सही समाधान है। यदि कोई समाधान नहीं मिलता है, तो अलग यादृच्छिक बनाएं {{tmath|T^*}} और फिर प्रयत्न करें। मान लीजिए कि टी के प्रत्येक सेल में अधिकतम आर तत्व हैं। फिर समाधान खोजने की संभावना (यदि कोई समाधान मौजूद है) यह संभावना है कि यादृच्छिक चयन प्रत्येक सेल से सही तत्व का चयन करेगा, जो है <math>(1/R)^3</math>. Conv3SUM चलाकर <math>R^3</math> कई बार, उच्च संभावना के साथ समाधान मिल जाएगा।
-दुर्भाग्य से, हमारे पास लीनियर परफेक्ट हैशिंग नहीं है, इसलिए हमें [[लगभग रैखिक हैश फ़ंक्शन]] का उपयोग करना होगा, यानी एक फ़ंक्शन h जैसे कि:
+दुर्भाग्य से, हमारे पास लीनियर परफेक्ट हैशिंग नहीं है, इसलिए हमें [[लगभग रैखिक हैश फ़ंक्शन]] का उपयोग करना होगा, यानी फ़ंक्शन h जैसे कि:
 :<math>h(x+y)=h(x)+h(y)</math> या
 :<math>h(x+y)=h(x)+h(y)+1</math>
@@ Line 109: / Line 109: @@
 == 3SUM-कठोरता ==
-किसी समस्या को 3SUM-हार्ड कहा जाता है यदि इसे [[उपवर्गिक समय]] में हल करने से 3SUM के लिए सबक्वाड्रैटिक-टाइम [[कलन विधि]] का पता चलता है। 3SUM-कठोरता की अवधारणा किसके द्वारा पेश की गई थी? {{harvtxt|Gajentaan|Overmars|1995}}. उन्होंने साबित किया कि [[कम्प्यूटेशनल ज्यामिति]] में समस्याओं का एक बड़ा वर्ग 3SUM-कठिन है, जिसमें निम्नलिखित भी शामिल हैं। (लेखक स्वीकार करते हैं कि इनमें से कई समस्याओं में अन्य शोधकर्ताओं का योगदान है।)
+किसी समस्या को 3SUM-हार्ड कहा जाता है यदि इसे [[उपवर्गिक समय]] में हल करने से 3SUM के लिए सबक्वाड्रैटिक-टाइम [[कलन विधि]] का पता चलता है। 3SUM-कठोरता की अवधारणा किसके द्वारा पेश की गई थी? {{harvtxt|Gajentaan|Overmars|1995}}. उन्होंने साबित किया कि [[कम्प्यूटेशनल ज्यामिति]] में समस्याओं का बड़ा वर्ग 3SUM-कठिन है, जिसमें निम्नलिखित भी शामिल हैं। (लेखक स्वीकार करते हैं कि इनमें से कई समस्याओं में अन्य शोधकर्ताओं का योगदान है।)
-* समतल में रेखाओं के एक समूह को देखते हुए, क्या तीन रेखाएँ एक बिंदु पर मिलती हैं?
+* समतल में रेखाओं के समूह को देखते हुए, क्या तीन रेखाएँ बिंदु पर मिलती हैं?
-* गैर-प्रतिच्छेदी अक्ष-समानांतर रेखा खंडों के एक सेट को देखते हुए, क्या कोई रेखा है जो उन्हें दो गैर-रिक्त उपसमुच्चय में अलग करती है?
+* गैर-प्रतिच्छेदी अक्ष-समानांतर रेखा खंडों के सेट को देखते हुए, क्या कोई रेखा है जो उन्हें दो गैर-रिक्त उपसमुच्चय में अलग करती है?
-* समतल में अनंत पट्टियों का एक सेट दिया गया है, क्या वे किसी दिए गए आयत को पूरी तरह से कवर करते हैं?
+* समतल में अनंत पट्टियों का सेट दिया गया है, क्या वे किसी दिए गए आयत को पूरी तरह से कवर करते हैं?
-* समतल में त्रिभुजों के एक सेट को देखते हुए, उनके माप की गणना करें।
+* समतल में त्रिभुजों के सेट को देखते हुए, उनके माप की गणना करें।
-* समतल में त्रिभुजों के एक समूह को देखते हुए, क्या उनके मिलन में कोई छेद है?
+* समतल में त्रिभुजों के समूह को देखते हुए, क्या उनके मिलन में कोई छेद है?
 * कई दृश्यता और गति नियोजन समस्याएं, जैसे,
-** अंतरिक्ष में क्षैतिज त्रिभुजों के एक सेट को देखते हुए, क्या किसी विशेष त्रिभुज को किसी विशेष बिंदु से देखा जा सकता है?
+** अंतरिक्ष में क्षैतिज त्रिभुजों के सेट को देखते हुए, क्या किसी विशेष त्रिभुज को किसी विशेष बिंदु से देखा जा सकता है?
-** विमान में गैर-प्रतिच्छेदी अक्ष-समानांतर रेखा खंड बाधाओं के एक सेट को देखते हुए, क्या किसी दिए गए रॉड को बाधाओं से टकराए बिना प्रारंभ और समाप्ति स्थितियों के बीच अनुवाद और घुमाव द्वारा स्थानांतरित किया जा सकता है?
+** विमान में गैर-प्रतिच्छेदी अक्ष-समानांतर रेखा खंड बाधाओं के सेट को देखते हुए, क्या किसी दिए गए रॉड को बाधाओं से टकराए बिना प्रारंभ और समाप्ति स्थितियों के बीच अनुवाद और घुमाव द्वारा स्थानांतरित किया जा सकता है?
-अब तक इस श्रेणी में आने वाली कई अन्य समस्याएं भी मौजूद हैं। एक उदाहरण [[एक्स + वाई छँटाई]] का निर्णय संस्करण है: संख्याओं के दिए गए सेट {{mvar|X}} और {{mvar|Y}} का {{mvar|n}}तत्व प्रत्येक, वहाँ हैं {{mvar|''n''²}} अलग {{math|''x'' + ''y''}} के लिए {{math|''x'' ∈ ''X'', ''y'' ∈ ''Y''}}?<ref>{{cite web |first1=Erik |last1=Demaine |author-link1=Erik Demaine |first2=Jeff |last2=Erickson |first3=Joseph |last3=O'Rourke |title=Problem 41: Sorting X + Y (Pairwise Sums) |date=20 August 2006 |access-date=23 September 2014 |website=The Open Problems Project |url=http://cs.smith.edu/~orourke/TOPP/P41.html}}</ref>
+अब तक इस श्रेणी में आने वाली कई अन्य समस्याएं भी मौजूद हैं। उदाहरण [[एक्स + वाई छँटाई]] का निर्णय संस्करण है: संख्याओं के दिए गए सेट {{mvar|X}} और {{mvar|Y}} का {{mvar|n}}तत्व प्रत्येक, वहाँ हैं {{mvar|''n''²}} अलग {{math|''x'' + ''y''}} के लिए {{math|''x'' ∈ ''X'', ''y'' ∈ ''Y''}}?<ref>{{cite web |first1=Erik |last1=Demaine |author-link1=Erik Demaine |first2=Jeff |last2=Erickson |first3=Joseph |last3=O'Rourke |title=Problem 41: Sorting X + Y (Pairwise Sums) |date=20 August 2006 |access-date=23 September 2014 |website=The Open Problems Project |url=http://cs.smith.edu/~orourke/TOPP/P41.html}}</ref>

Anonymous

Search

3 सम: Difference between revisions

Namespaces

More

Page actions

Revision as of 16:50, 17 July 2023