3 सम: Difference between revisions

From Vigyanwiki
No edit summary
No edit summary
Line 1: Line 1:
{{Short description|Problem in computational complexity theory}}
{{Short description|Problem in computational complexity theory}}
{{redirects|3sum|the malt beverage|Comparison of alcopops#Beer-based}}
{{redirects|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>?}}
{{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}}.
[[कम्प्यूटेशनल जटिलता सिद्धांत]] में, 3सम समस्या पूछती है कि क्या दिया गया समुच्चय <math>n</math> वास्तविक संख्याओं में तीन तत्व होते हैं जिनका योग शून्य होता है। सामान्यीकृत संस्करण, k-सम, k संख्याओं पर समान प्रश्न पूछता है। 3सम को सरलता से हल किया जा सकता है इस प्रकार <math>O(n^2)</math> समय, और मिलान <math>\Omega(n^{\lceil k/2 \rceil})</math> गणना के कुछ विशेष मॉडलों में निचली सीमाएं ज्ञात होती हैं {{harv|एरिक्सन|1999}}.


यह अनुमान लगाया गया था कि 3SUM के लिए किसी भी नियतात्मक एल्गोरिदम की आवश्यकता होती है <math> \Omega(n^2) </math> समय।
यह अनुमान लगाया गया था कि 3सम के लिए किसी भी नियतात्मक एल्गोरिदम <math> \Omega(n^2) </math> समय की आवश्यकता होती है। इस प्रकार 2014 में, मूल 3सम अनुमान का एलन ग्रोनलुंड और सेठ पेटी ने खंडन किया था, जिन्होंने नियतात्मक एल्गोरिदम दिया था जो 3सम को हल करता है <math>O(n^2 / ({\log n} / {\log \log n})^{2/3})</math> समय {{sfn|Grønlund|Pettie|2014}} इसके अतिरिक्त, ग्रोनलुंड और पेटी ने दिखाया कि 3सम की 4-निर्णय ट्री मॉडल रैखिक निर्णय ट्री जटिलता <math> O(n^{3/2}\sqrt{\log n}) </math> है इसके पश्चात् इन सीमाओं में सुधार किया गया था।{{sfn|Freund|2017}}{{sfn|Gold|Sharir|2017}}{{sfn|Chan|2018}}
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>.
3सम के लिए वर्तमान सबसे प्रसिद्ध एल्गोरिदम <math>O(n^2 (\log \log n)^{O(1)} / {\log^2 n}) </math> चलता है  {{sfn|Chan|2018}} केन, लवेट और मोरन ने दिखाया कि 6-निर्णय ट्री मॉडल 3सम की रैखिक निर्णय ट्री <math>O(n{\log^2 n})</math> जटिलता है {{sfn|Kane|Lovett|Moran|2018}} पश्चात् वाली सीमा कड़ी है (लघुगणकीय कारक तक) यह अभी भी अनुमान लगाया गया है कि 3सम का समाधान <math>O(n^{2-\Omega(1)})</math> नहीं हो सका है।<ref name="kpp14" />
बाद में इन सीमाओं में सुधार किया गया।{{sfn|Freund|2017}}{{sfn|Gold|Sharir|2017}}{{sfn|Chan|2018}}
 
3SUM के लिए वर्तमान सबसे प्रसिद्ध एल्गोरिदम चलता है <math>O(n^2 (\log \log n)^{O(1)} / {\log^2 n}) </math> समय।{{sfn|Chan|2018}}
जब श्रेणी में तत्व पूर्णांक हों <math>[-N, \dots, N]</math>, 3सम में हल <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>
केन, लवेट और मोरन ने दिखाया कि 6-निर्णय वृक्ष मॉडल#3SUM की रैखिक निर्णय वृक्ष जटिलता है <math>O(n{\log^2 n})</math>.{{sfn|Kane|Lovett|Moran|2018}} बाद वाली सीमा कड़ी है (लघुगणकीय कारक तक)।
यह अभी भी अनुमान लगाया गया है कि 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>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> है कंप्यूटिंग के पूर्णांक (शब्द रैम) मॉडल में, 3सम <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 के लिए करें
  i = 0 से n - 2 के लिए करें
   ए = एस[आई];
   ए = एस[आई];
Line 62: Line 61:
* संशोधित सरणी में, 3 तत्व खोजें जिनका योग 0 है।
* संशोधित सरणी में, 3 तत्व खोजें जिनका योग 0 है।


उदाहरण के लिए, यदि A=[1,2,3,4] और यदि आपको C=4 के लिए 3SUM खोजने के लिए कहा जाए, तो A के सभी तत्वों में से 4/3 घटाएं, और इसे सामान्य 3sum तरीके से हल करें, अर्थात। , {{tmath|1=(a-C/3) + (b-C/3) + (c-C/3) = 0}}.
उदाहरण के लिए, यदि A=[1,2,3,4] और यदि आपको C=4 के लिए 3सम खोजने के लिए कहा जाए, तो A के सभी तत्वों में से 4/3 घटाएं, और इसे सामान्य 3सम तरीके से हल करें, अर्थात। , {{tmath|1=(a-C/3) + (b-C/3) + (c-C/3) = 0}}.


=== तीन अलग-अलग सरणियाँ ===
=== तीन अलग-अलग सरणियाँ ===
एक ही सारणी में 3 संख्याओं को खोजने के बजाय, हम उन्हें 3 अलग-अलग सारणियों में खोज सकते हैं। यानी, तीन सरणियाँ X, Y और Z दी गई हैं, तीन संख्याएँ खोजें {{math|''a''∈''X'', ''b''∈''Y'', ''c''∈''Z''}}, ऐसा है कि {{tmath|a+b+c{{=}}0}}. 1-सरणी वैरिएंट 3SUM×1 और 3-सरणी वैरिएंट 3SUM×3 को कॉल करें।
एक ही सारणी में 3 संख्याओं को खोजने के बजाय, हम उन्हें 3 अलग-अलग सारणियों में खोज सकते हैं। यानी, तीन सरणियाँ X, Y और Z दी गई हैं, तीन संख्याएँ खोजें {{math|''a''∈''X'', ''b''∈''Y'', ''c''∈''Z''}}, ऐसा है कि {{tmath|a+b+c{{=}}0}}. 1-सरणी वैरिएंट 3सम×1 और 3-सरणी वैरिएंट 3सम×3 को कॉल करें।


3SUM×1 के लिए सॉल्वर दिए जाने पर, 3SUM×3 समस्या को निम्नलिखित तरीके से हल किया जा सकता है (यह मानते हुए कि सभी तत्व पूर्णांक हैं):
3सम×1 के लिए सॉल्वर दिए जाने पर, 3सम×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}}.
* 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}}.
* तीन तत्वों को खोजने के लिए 3सम×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}}.
* वापस करना {{tmath|a \gets (a'-1)/10,\ b \gets (b'-2)/10,\ c \gets (c'+3)/10}}.
जिस तरह से हमने सरणियों को रूपांतरित किया, इसकी गारंटी है {{math|''a''∈''X'', ''b''∈''Y'', ''c''∈''Z''}}.<ref>For a reduction in the other direction, see [https://cs.stackexchange.com/q/37888 Variants of the 3-sum problem].</ref>
जिस तरह से हमने सरणियों को रूपांतरित किया, इसकी गारंटी है {{math|''a''∈''X'', ''b''∈''Y'', ''c''∈''Z''}}.<ref>For a reduction in the other direction, see [https://cs.stackexchange.com/q/37888 Variants of the 3-sum problem].</ref>
Line 78: Line 77:
सरणी के मनमाने तत्वों की तलाश करने के बजाय:
सरणी के मनमाने तत्वों की तलाश करने के बजाय:
:<math>S[k]=S[i]+S[j]</math>
:<math>S[k]=S[i]+S[j]</math>
कनवल्शन 3sum समस्या (Conv3SUM) विशिष्ट स्थानों में तत्वों की तलाश करती है:<ref name=patrascu10>{{Cite conference | doi = 10.1145/1806689.1806772| title = गतिशील समस्याओं के लिए बहुपद निचली सीमा की ओर| conference = Proceedings of the 42nd ACM symposium on Theory of computing - STOC '10| pages = 603| year = 2010| last1 = Patrascu | first1 = M. | isbn = 9781450300506}}</ref>
कनवल्शन 3सम समस्या (Conv3सम) विशिष्ट स्थानों में तत्वों की तलाश करती है:<ref name=patrascu10>{{Cite conference | doi = 10.1145/1806689.1806772| title = गतिशील समस्याओं के लिए बहुपद निचली सीमा की ओर| conference = Proceedings of the 42nd ACM symposium on Theory of computing - STOC '10| pages = 603| year = 2010| last1 = Patrascu | first1 = M. | isbn = 9781450300506}}</ref>
:<math>S[i+j]=S[i]+S[j]</math>
:<math>S[i+j]=S[i]+S[j]</math>




==== Conv3SUM से 3SUM तक कमी ====
==== Conv3सम से 3सम तक कमी ====
3SUM के लिए सॉल्वर दिए जाने पर, Conv3SUM समस्या को निम्नलिखित तरीके से हल किया जा सकता है।<ref name=patrascu10/>* नई सरणी टी परिभाषित करें, जैसे कि प्रत्येक सूचकांक के लिए: <math>T[i]=2n S[i]+i</math> (जहाँ n सरणी में तत्वों की संख्या है, और सूचकांक 0 से n-1 तक चलते हैं)।
3सम के लिए सॉल्वर दिए जाने पर, Conv3सम समस्या को निम्नलिखित तरीके से हल किया जा सकता है।<ref name=patrascu10/>* नई सरणी टी परिभाषित करें, जैसे कि प्रत्येक सूचकांक के लिए: <math>T[i]=2n S[i]+i</math> (जहाँ n सरणी में तत्वों की संख्या है, और सूचकांक 0 से n-1 तक चलते हैं)।
* सरणी T पर 3SUM हल करें।
* सरणी T पर 3सम हल करें।


शुद्धता प्रमाण:
शुद्धता प्रमाण:
* यदि मूल सारणी में त्रिगुण है <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>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>, इसलिए यह समाधान 3सम द्वारा 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 पर Conv3सम के लिए वैध समाधान है।


==== 3SUM से Conv3SUM तक कमी ====
==== 3सम से Conv3सम तक कमी ====
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/>
Conv3सम के लिए सॉल्वर दिए जाने पर, 3सम समस्या को निम्नलिखित तरीके से हल किया जा सकता है।<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 ऐसा है कि:
Line 97: Line 96:
मान लीजिए कि सभी तत्व श्रेणी में पूर्णांक हैं: 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>
:<math>T[h(x)] = x</math>
प्रारंभ में, मान लें कि मैपिंग अद्वितीय हैं (अर्थात टी में प्रत्येक कोशिका एस से केवल ही तत्व स्वीकार करती है)। T पर Conv3SUM को हल करें। अभी:
प्रारंभ में, मान लें कि मैपिंग अद्वितीय हैं (अर्थात टी में प्रत्येक कोशिका एस से केवल ही तत्व स्वीकार करती है)। T पर Conv3सम को हल करें। अभी:
* यदि 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 सॉल्वर द्वारा पाया जाएगा।
* यदि 3सम के लिए कोई समाधान है: <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 पर Conv3सम सॉल्वर द्वारा पाया जाएगा।
* इसके विपरीत, यदि T पर Conv3SUM पाया जाता है, तो जाहिर तौर पर यह S पर 3SUM समाधान से मेल खाता है क्योंकि T केवल S का क्रमपरिवर्तन है।
* इसके विपरीत, यदि T पर Conv3सम पाया जाता है, तो जाहिर तौर पर यह S पर 3सम समाधान से मेल खाता है क्योंकि 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 के प्रत्येक सेल से यादृच्छिक तत्व का चयन करके, और Conv3सम को चालू करें {{tmath|T^*}}. यदि कोई समाधान मिल जाता है, तो यह S पर 3सम के लिए सही समाधान है। यदि कोई समाधान नहीं मिलता है, तो अलग यादृच्छिक बनाएं {{tmath|T^*}} और फिर प्रयत्न करें। मान लीजिए कि टी के प्रत्येक सेल में अधिकतम आर तत्व हैं। फिर समाधान खोजने की संभावना (यदि कोई समाधान मौजूद है) यह संभावना है कि यादृच्छिक चयन प्रत्येक सेल से सही तत्व का चयन करेगा, जो है <math>(1/R)^3</math>. Conv3सम चलाकर <math>R^3</math> कई बार, उच्च संभावना के साथ समाधान मिल जाएगा।


दुर्भाग्य से, हमारे पास लीनियर परफेक्ट हैशिंग नहीं है, इसलिए हमें [[लगभग रैखिक हैश फ़ंक्शन]] का उपयोग करना होगा, यानी फ़ंक्शन h जैसे कि:
दुर्भाग्य से, हमारे पास लीनियर परफेक्ट हैशिंग नहीं है, इसलिए हमें [[लगभग रैखिक हैश फ़ंक्शन]] का उपयोग करना होगा, यानी फ़ंक्शन h जैसे कि:
:<math>h(x+y)=h(x)+h(y)</math> या
:<math>h(x+y)=h(x)+h(y)</math> या
:<math>h(x+y)=h(x)+h(y)+1</math>
:<math>h(x+y)=h(x)+h(y)+1</math>
इसके लिए S के तत्वों को T में कॉपी करते समय उनकी नकल करने की आवश्यकता होती है, यानी, प्रत्येक तत्व को रखना होता है <math>x\in S</math> में दोनों <math>T[h(x)]</math> (पहले की तरह) और अंदर <math>T[h(x)]-1</math>. इसलिए प्रत्येक सेल में 2R तत्व होंगे, और हमें Conv3SUM चलाना होगा <math>(2R)^3</math> बार.
इसके लिए S के तत्वों को T में कॉपी करते समय उनकी नकल करने की आवश्यकता होती है, यानी, प्रत्येक तत्व को रखना होता है <math>x\in S</math> में दोनों <math>T[h(x)]</math> (पहले की तरह) और अंदर <math>T[h(x)]-1</math>. इसलिए प्रत्येक सेल में 2R तत्व होंगे, और हमें Conv3सम चलाना होगा <math>(2R)^3</math> बार.


== 3SUM-कठोरता ==
== 3सम-कठोरता ==
किसी समस्या को 3SUM-हार्ड कहा जाता है यदि इसे [[उपवर्गिक समय]] में हल करने से 3SUM के लिए सबक्वाड्रैटिक-टाइम [[कलन विधि]] का पता चलता है। 3SUM-कठोरता की अवधारणा किसके द्वारा पेश की गई थी? {{harvtxt|Gajentaan|Overmars|1995}}. उन्होंने साबित किया कि [[कम्प्यूटेशनल ज्यामिति]] में समस्याओं का बड़ा वर्ग 3SUM-कठिन है, जिसमें निम्नलिखित भी शामिल हैं। (लेखक स्वीकार करते हैं कि इनमें से कई समस्याओं में अन्य शोधकर्ताओं का योगदान है।)
किसी समस्या को 3सम-हार्ड कहा जाता है यदि इसे [[उपवर्गिक समय]] में हल करने से 3सम के लिए सबक्वाड्रैटिक-टाइम [[कलन विधि]] का पता चलता है। 3सम-कठोरता की अवधारणा किसके द्वारा पेश की गई थी? {{harvtxt|Gajentaan|Overmars|1995}}. उन्होंने साबित किया कि [[कम्प्यूटेशनल ज्यामिति]] में समस्याओं का बड़ा वर्ग 3सम-कठिन है, जिसमें निम्नलिखित भी शामिल हैं। (लेखक स्वीकार करते हैं कि इनमें से कई समस्याओं में अन्य शोधकर्ताओं का योगदान है।)


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


अब तक इस श्रेणी में आने वाली कई अन्य समस्याएं भी मौजूद हैं। उदाहरण [[एक्स + वाई छँटाई]] का निर्णय संस्करण है: संख्याओं के दिए गए सेट {{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>




== यह भी देखें ==
== यह भी देखें ==
* सबसेट योग समस्या
* सबसमुच्चय योग समस्या


== टिप्पणियाँ ==
== टिप्पणियाँ ==

Revision as of 16:59, 17 July 2023

"3सम" redirects here. For माल्ट पेय, see एल्कोपॉप्स की तुलना § बीयर-आधारित.
Unsolved problem in computer science:

Is there an algorithm to solve the 3SUM problem in time , for some ?

(more unsolved problems in computer science)

कम्प्यूटेशनल जटिलता सिद्धांत में, 3सम समस्या पूछती है कि क्या दिया गया समुच्चय वास्तविक संख्याओं में तीन तत्व होते हैं जिनका योग शून्य होता है। सामान्यीकृत संस्करण, k-सम, k संख्याओं पर समान प्रश्न पूछता है। 3सम को सरलता से हल किया जा सकता है इस प्रकार समय, और मिलान गणना के कुछ विशेष मॉडलों में निचली सीमाएं ज्ञात होती हैं (एरिक्सन 1999).

यह अनुमान लगाया गया था कि 3सम के लिए किसी भी नियतात्मक एल्गोरिदम समय की आवश्यकता होती है। इस प्रकार 2014 में, मूल 3सम अनुमान का एलन ग्रोनलुंड और सेठ पेटी ने खंडन किया था, जिन्होंने नियतात्मक एल्गोरिदम दिया था जो 3सम को हल करता है समय [1] इसके अतिरिक्त, ग्रोनलुंड और पेटी ने दिखाया कि 3सम की 4-निर्णय ट्री मॉडल रैखिक निर्णय ट्री जटिलता है इसके पश्चात् इन सीमाओं में सुधार किया गया था।[2]