3 सम

"3sum" redirects here. For the malt beverage, see Comparison of alcopops § Beer-based.

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})$ समय। इसके अतिरिक्त, ग्रोनलुंड और पेटी ने दिखाया कि 3SUM की 4-निर्णय वृक्ष मॉडल#रैखिक निर्णय वृक्ष जटिलता है $O(n^{3/2}{\sqrt {\log n}})$. बाद में इन सीमाओं में सुधार किया गया। 3SUM के लिए वर्तमान सबसे प्रसिद्ध एल्गोरिदम चलता है $O(n^{2}(\log \log n)^{O(1)}/{\log ^{2}n})$ समय। केन, लवेट और मोरन ने दिखाया कि 6-निर्णय वृक्ष मॉडल#3SUM की रैखिक निर्णय वृक्ष जटिलता है $O(n{\log ^{2}n})$. बाद वाली सीमा कड़ी है (लघुगणकीय कारक तक)। यह अभी भी अनुमान लगाया गया है कि 3SUM का समाधान नहीं हो सका है $O(n^{2-\Omega (1)})$ अपेक्षित समय।

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

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

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

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

i = 0 से n - 2 के लिए करें
    ए = एस[आई];
    प्रारंभ = मैं + 1;
    अंत = एन - 1;
    जबकि (प्रारंभ <अंत) करते हैं
        बी = एस[प्रारंभ]
        सी = एस[अंत];
        यदि (ए + बी + सी == 0) तो
            आउटपुट ए, बी, सी;
            // शून्य के योग वाले सभी त्रिक संयोजनों की खोज जारी रखें।
            // हमें अंत और प्रारंभ दोनों को एक साथ अपडेट करने की आवश्यकता है क्योंकि सरणी मान अलग-अलग हैं।
            प्रारंभ = प्रारंभ + 1;
            अंत = अंत - 1;
        अन्यथा यदि (ए + बी + सी > 0) तो
            अंत = अंत - 1;
        अन्य
            प्रारंभ = प्रारंभ + 1;
    अंत
अंत

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

 -25 -10 -7 -3 2 4 8 10 (a +बी+सी==-25)
 -25 -10 -7 -3 2 4 8 10 (ए +बी+सी==-22)
 . . .
 -25 -10 -7 -3 2 4 8 10 (a +बी+सी==-7)
 -25 -10 -7 -3 2 4 8 10 (ए +बी+सी==-7)
 -25 -10 -7 -3 2 4 8 10 (ए +बी+सी==-3)
 -25 -10 -7 -3 2 4 8 10 (a +बी+सी==2)
 -25 -10 -7 -3 2 4 8 10 (a +बी+सी==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 के लिए 3SUM खोजने के लिए कहा जाए, तो A के सभी तत्वों में से 4/3 घटाएं, और इसे सामान्य 3sum तरीके से हल करें, अर्थात। , $(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-सरणी वैरिएंट 3SUM×1 और 3-सरणी वैरिएंट 3SUM×3 को कॉल करें।

3SUM×1 के लिए एक सॉल्वर दिए जाने पर, 3SUM×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 का एक संयोजन है।
• तीन तत्वों को खोजने के लिए 3SUM×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]$

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

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

Conv3SUM से 3SUM तक कमी

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

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

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

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

3SUM से Conv3SUM तक कमी

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

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

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

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

$T[h(x)]=x$

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

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

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

3SUM-कठोरता

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

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

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