3 सम

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

Unsolved problem in कंप्यूटर विज्ञान:

क्या 3सम समस्या को समय पर हल करने के लिए कोई एल्गोरिदम है? $O(n^{2-\epsilon })$, कुछ के लिए $\epsilon >0$?

(more unsolved problems in कंप्यूटर विज्ञान)

कम्प्यूटेशनल जटिलता सिद्धांत में, 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})$ है.

सॉर्ट(s);

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 है। पूर्णांक के लिए हैश तालिका खोजने के लिए मूल एल्गोरिदम को संशोधित करना सबसे सरल विधि $(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सम समस्या (कन्व3सम) विशिष्ट स्थानों में तत्वों की खोज करती है:

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

कन्व3सम से 3सम तक कमी

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

नई सरणी टी परिभाषित करें, जैसे कि प्रत्येक सूचकांक के लिए: $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 पर कन्व3सम के लिए वैध समाधान है।

3सम से कन्व3सम तक कमी

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

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

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

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

$T[h(x)]=x$

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

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

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

3सम-कठोरता

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

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

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

यह भी देखें

• उपसमुच्चय योग समस्या

संदर्भ

• 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).