3 सम

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

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)

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

यह अनुमान लगाया गया था कि 3सम के लिए किसी भी नियतात्मक एल्गोरिदम $\Omega (n^{2})$ समय की आवश्यकता होती है। इस प्रकार 2014 में, मूल 3सम अनुमान का एलन ग्रोनलुंड और सेठ पेटी ने खंडन किया था, जिन्होंने नियतात्मक एल्गोरिदम दिया था जो 3सम को हल करता है $O(n^{2}/({\log n}/{\log \log n})^{2/3})$ समय इसके अतिरिक्त, ग्रोनलुंड और पेटी ने दिखाया कि 3सम की 4-निर्णय ट्री मॉडल रैखिक निर्णय ट्री जटिलता $O(n^{3/2}{\sqrt {\log n}})$ है इसके पश्चात् इन सीमाओं में सुधार किया गया था।

3सम के लिए वर्तमान सबसे प्रसिद्ध एल्गोरिदम $O(n^{2}(\log \log n)^{O(1)}/{\log ^{2}n})$ चलता है केन, लवेट और मोरन ने दिखाया कि 6-निर्णय ट्री मॉडल 3सम की रैखिक निर्णय ट्री $O(n{\log ^{2}n})$ जटिलता है पश्चात् वाली सीमा कड़ी है (लघुगणकीय कारक तक) यह अभी भी अनुमान लगाया गया है कि 3सम का समाधान $O(n^{2-\Omega (1)})$ नहीं हो सका है।

जब श्रेणी में तत्व पूर्णांक हों $[-N,\dots ,N]$, 3सम में हल $O(n+N\log N)$ किया जा सकता है इनपुट समुच्चय का प्रतिनिधित्व करके समय $S$ बिट सरणी के रूप में, समुच्चय की गणना करना $S+S$ तेज फूरियर रूपांतरण का उपयोग करते हुए असतत कनवल्शन के रूप में सभी जोड़ीवार योगों की, और अंत में इस समुच्चय $S$ की तुलना की गई थी

द्विघात एल्गोरिथ्म

मान लीजिए कि इनपुट ऐरे $S[0..n-1]$ है कंप्यूटिंग के पूर्णांक (शब्द रैम) मॉडल में, 3सम $O(n^{2})$ को हल किया जा सकता है प्रत्येक संख्या डालने पर औसतन समय $S[i]$ हैश तालिका में, और फिर, प्रत्येक सूचकांक के लिए $i$ और $j$, जाँच कर रहा है कि हैश तालिका में पूर्णांक है या नहीं $-(S[i]+S[j])$ है

कंप्यूटिंग या वास्तविक रैम के कंप्यूटर प्रोग्रामिंग आधारित मॉडल में ही समय में समस्या को हल करना भी संभव है, जिसके लिए हैशिंग की अनुमति नहीं है। नीचे दिया गया एल्गोरिदम पहले इनपुट ऐरे को सॉर्ट करता है और फिर सावधानीपूर्वक सभी संभावित जोड़ियों का परीक्षण करता है, जिससे क्रमबद्ध सूची में जोड़ियों के लिए बाइनरी खोज की आवश्यकता से बचा जा सकता है, जिससे सबसे व्यर्थ स्थिति प्राप्त होती है। समय, इस प्रकार $O(n^{2})$ है.

सॉर्ट(एस);

sort(S);
for i = 0 to n - 2 do
    a = S[i];
    start = i + 1;
    end = n - 1;
    while (start < end) do
        b = S[start]
        c = S[end];
        if (a + b + c == 0) then
            output a, b, c;
            // Continue search for all triplet combinations summing to zero.
            // We need to update both end and start together since the array values are distinct.
            start = start + 1;
            end = end - 1;
        else if (a + b + c > 0) then
            end = end - 1;
        else
            start = start + 1;
    end
end

निम्नलिखित उदाहरण छोटे क्रमबद्ध सरणी पर इस एल्गोरिदम के निष्पादन को दिखाता है। a के वर्तमान मान लाल रंग में दिखाए गए हैं, b और c के मान मैजेंटा में दिखाए गए हैं।

 -25 -10 -7 -3 2 4 8 10  (a+b+c==-25)
 -25 -10 -7 -3 2 4 8 10  (a+b+c==-22)
 . . .
 -25 -10 -7 -3 2 4 8 10  (a+b+c==-7)
 -25 -10 -7 -3 2 4 8 10  (a+b+c==-7)
 -25 -10 -7 -3 2 4 8 10  (a+b+c==-3)
 -25 -10 -7 -3 2 4 8 10  (a+b+c==2)
 -25 -10 -7 -3 2 4 8 10  (a+b+c==0)

एल्गोरिथम की शुद्धता इस प्रकार देखी जा सकती है। मान लीजिए कि हमारे पास समाधान है a + b + c = 0. चूंकि सूचक केवल ही दिशा में चलते हैं, हम एल्गोरिदम को तब तक चला सकते हैं जब तक कि सबसे बाईं ओर का सूचक a की ओर इंगित न कर दे। एल्गोरिथम को तब तक चलाएँ जब तक कि शेष संकेतकों में से कोई b या c, जो भी पहले हो, को इंगित न कर दे। तब एल्गोरिथ्म तब तक चलेगा जब तक अंतिम सूचक सकारात्मक समाधान देते हुए शेष पद की ओर इशारा नहीं करता।

वेरिएंट

गैर-शून्य योग

उन संख्याओं की तलाश करने के बजाय जिनका योग 0 है, उन संख्याओं की तलाश करना संभव है जिनका योग कोई स्थिर सी है। पूर्णांक के लिए हैश तालिका खोजने के लिए मूल एल्गोरिदम को संशोधित करना सबसे आसान तरीका होगा $(C-(S[i]+S[j]))$.

दूसरी विधि:

• इनपुट सरणी के सभी तत्वों से C/3 घटाएँ।
• संशोधित सरणी में, 3 तत्व खोजें जिनका योग 0 है।

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

तीन अलग-अलग सरणियाँ

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

3सम×1 के लिए सॉल्वर दिए जाने पर, 3सम×3 समस्या को निम्नलिखित तरीके से हल किया जा सकता है (यह मानते हुए कि सभी तत्व पूर्णांक हैं):

• X, Y और Z में प्रत्येक तत्व के लिए, समुच्चय करें: $X[i]\gets X[i]*10+1$, $Y[i]\gets Y[i]*10+2$, $Z[i]\gets Z[i]*10-3$.
• मान लीजिए S, सारणियों X, Y और Z का संयोजन है।
• तीन तत्वों को खोजने के लिए 3सम×1 ओरेकल का उपयोग करें $a'\in S,\ b'\in S,\ c'\in S$ ऐसा है कि $a'+b'+c'=0$.
• वापस करना $a\gets (a'-1)/10,\ b\gets (b'-2)/10,\ c\gets (c'+3)/10$.

जिस तरह से हमने सरणियों को रूपांतरित किया, इसकी गारंटी है a∈X, b∈Y, c∈Z.

कनवल्शन योग

सरणी के मनमाने तत्वों की तलाश करने के बजाय:

$S[k]=S[i]+S[j]$

कनवल्शन 3सम समस्या (Conv3सम) विशिष्ट स्थानों में तत्वों की तलाश करती है:

$S[i+j]=S[i]+S[j]$

Conv3सम से 3सम तक कमी

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

• सरणी T पर 3सम हल करें।

शुद्धता प्रमाण:

• यदि मूल सारणी में त्रिगुण है $S[i+j]=S[i]+S[j]$, तब $T[i+j]=2nS[i+j]+i+j=(2nS[i]+i)+(2nS[j]+j)=T[i]+T[j]$, इसलिए यह समाधान 3सम द्वारा T पर पाया जाएगा।
• इसके विपरीत, यदि नए ऐरे में ट्रिपल विथ है $T[k]=T[i]+T[j]$, तब $2nS[k]+k=2n(S[i]+S[j])+(i+j)$. क्योंकि $i+j<2n$, अनिवार्य रूप से $S[k]=S[i]+S[j]$ और $k=i+j$, इसलिए यह S पर Conv3सम के लिए वैध समाधान है।

3सम से Conv3सम तक कमी

Conv3सम के लिए सॉल्वर दिए जाने पर, 3सम समस्या को निम्नलिखित तरीके से हल किया जा सकता है।

कमी हैश फंकशन का उपयोग करती है। पहले सन्निकटन के रूप में, मान लें कि हमारे पास रैखिक हैश फ़ंक्शन है, यानी फ़ंक्शन h ऐसा है कि:

$h(x+y)=h(x)+h(y)$

मान लीजिए कि सभी तत्व श्रेणी में पूर्णांक हैं: 0...N-1, और फ़ंक्शन h प्रत्येक तत्व को सूचकांकों की छोटी श्रेणी में तत्व में मैप करता है: 0...n-1। नया ऐरे टी बनाएं और एस के प्रत्येक तत्व को टी में उसके हैश मान पर भेजें, यानी, एस में प्रत्येक एक्स के लिए($\forall x\in S$):

$T[h(x)]=x$

प्रारंभ में, मान लें कि मैपिंग अद्वितीय हैं (अर्थात टी में प्रत्येक कोशिका एस से केवल ही तत्व स्वीकार करती है)। T पर Conv3सम को हल करें। अभी:

• यदि 3सम के लिए कोई समाधान है: $z=x+y$, तब: $T[h(z)]=T[h(x)]+T[h(y)]$ और $h(z)=h(x)+h(y)$, इसलिए यह समाधान T पर Conv3सम सॉल्वर द्वारा पाया जाएगा।
• इसके विपरीत, यदि T पर Conv3सम पाया जाता है, तो जाहिर तौर पर यह S पर 3सम समाधान से मेल खाता है क्योंकि T केवल S का क्रमपरिवर्तन है।

यह आदर्श समाधान काम नहीं करता है, क्योंकि कोई भी हैश फ़ंक्शन S के कई अलग-अलग तत्वों को T के ही सेल में मैप कर सकता है। चाल सरणी बनाने की है $T^{*}$ T के प्रत्येक सेल से यादृच्छिक तत्व का चयन करके, और Conv3सम को चालू करें $T^{*}$. यदि कोई समाधान मिल जाता है, तो यह S पर 3सम के लिए सही समाधान है। यदि कोई समाधान नहीं मिलता है, तो अलग यादृच्छिक बनाएं $T^{*}$ और फिर प्रयत्न करें। मान लीजिए कि टी के प्रत्येक सेल में अधिकतम आर तत्व हैं। फिर समाधान खोजने की संभावना (यदि कोई समाधान मौजूद है) यह संभावना है कि यादृच्छिक चयन प्रत्येक सेल से सही तत्व का चयन करेगा, जो है $(1/R)^{3}$. Conv3सम चलाकर $R^{3}$ कई बार, उच्च संभावना के साथ समाधान मिल जाएगा।

दुर्भाग्य से, हमारे पास लीनियर परफेक्ट हैशिंग नहीं है, इसलिए हमें लगभग रैखिक हैश फ़ंक्शन का उपयोग करना होगा, यानी फ़ंक्शन h जैसे कि:

$h(x+y)=h(x)+h(y)$ या

$h(x+y)=h(x)+h(y)+1$

इसके लिए S के तत्वों को T में कॉपी करते समय उनकी नकल करने की आवश्यकता होती है, यानी, प्रत्येक तत्व को रखना होता है $x\in S$ में दोनों $T[h(x)]$ (पहले की तरह) और अंदर $T[h(x)]-1$. इसलिए प्रत्येक सेल में 2R तत्व होंगे, और हमें Conv3सम चलाना होगा $(2R)^{3}$ बार.

3सम-कठोरता

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

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

अब तक इस श्रेणी में आने वाली कई अन्य समस्याएं भी मौजूद हैं। उदाहरण एक्स + वाई छँटाई का निर्णय संस्करण है: संख्याओं के दिए गए समुच्चय X और Y का nतत्व प्रत्येक, वहाँ हैं n² अलग x + y के लिए x ∈ X, y ∈ Y?

यह भी देखें

• सबसमुच्चय योग समस्या

संदर्भ

• Kane, Daniel M.; Lovett, Shachar; Moran, Shay (2018). "Near-optimal linear decision trees for k-SUM and related problems". Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing (STOC): 554–563. arXiv:1705.01720. doi:10.1145/3188745.3188770. ISBN 9781450355599. S2CID 30368541.
• Chan, Timothy M. (2018), "More Logarithmic-Factor Speedups for 3SUM, (median, +)-Convolution, and Some Geometric 3SUM-Hard Problems", Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA): 881–897, doi:10.1137/1.9781611975031.57, ISBN 978-1-61197-503-1
• Grønlund, A.; Pettie, S. (2014). Threesomes, Degenerates, and Love Triangles. 2014 IEEE 55th Annual Symposium on Foundations of Computer Science. p. 621. arXiv:1404.0799. Bibcode:2014arXiv1404.0799G. doi:10.1109/FOCS.2014.72. ISBN 978-1-4799-6517-5.
• Freund, Ari (2017), "Improved Subquadratic 3SUM", Algorithmica, 44 (2): 440–458, doi:10.1007/s00453-015-0079-6, S2CID 253979651.
• Gold, Omer; Sharir, Micha (2017), "Improved Bounds for 3SUM, k-SUM, and Linear Degeneracy", In Proc. 25th Annual European Symposium on Algorithms (ESA), LIPIcs, 87: 42:1–42:13, doi:10.4230/LIPIcs.ESA.2017.42, S2CID 691387
• Baran, Ilya; Demaine, Erik D.; Pătraşcu, Mihai (2008), "Subquadratic algorithms for 3SUM", Algorithmica, 50 (4): 584–596, doi:10.1007/s00453-007-9036-3, S2CID 9855995.
• Demaine, Erik D.; Mitchell, Joseph S. B.; O'Rourke, Joseph (July 2005), "Problem 11: 3SUM Hard Problems", The Open Problems Project, archived from the original on 2012-12-15, retrieved 2008-09-02.
• Erickson, Jeff (1999), "Lower bounds for linear satisfiability problems", Chicago Journal of Theoretical Computer Science, MIT Press, 1999.
• Gajentaan, Anka; Overmars, Mark H. (1995), "On a class of O(n²) problems in computational geometry", Computational Geometry: Theory and Applications, 5 (3): 165–185, doi:10.1016/0925-7721(95)00022-2, hdl:1874/17058.
• King, James (2004), A survey of 3SUM-hard problems (PDF).