3 सम

From Vigyanwiki
Revision as of 17:02, 17 July 2023 by alpha>Neetua08
Unsolved problem in computer science:

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

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

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

3सम के लिए वर्तमान सबसे प्रसिद्ध एल्गोरिदम चलता है [4] केन, लवेट और मोरन ने दिखाया कि 6-निर्णय ट्री मॉडल 3सम की रैखिक निर्णय ट्री जटिलता है [5] पश्चात् वाली सीमा कड़ी है (लघुगणकीय कारक तक) यह अभी भी अनुमान लगाया गया है कि 3सम का समाधान नहीं हो सका है।[6]

जब श्रेणी में तत्व पूर्णांक हों , 3सम में हल किया जा सकता है इनपुट समुच्चय का प्रतिनिधित्व करके समय बिट सरणी के रूप में, समुच्चय की गणना करना तेज फूरियर रूपांतरण का उपयोग करते हुए असतत कनवल्शन के रूप में सभी जोड़ीवार योगों की, और अंत में इस समुच्चय की तुलना की गई थी [7]


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

मान लीजिए कि इनपुट ऐरे है कंप्यूटिंग के पूर्णांक (शब्द रैम) मॉडल में, 3सम को हल किया जा सकता है प्रत्येक संख्या डालने पर औसतन समय हैश तालिका में, और फिर, प्रत्येक सूचकांक के लिए और , जाँच कर रहा है कि हैश तालिका में पूर्णांक है या नहीं है

कंप्यूटिंग या वास्तविक रैम के कंप्यूटर प्रोग्रामिंग आधारित मॉडल में ही समय में समस्या को हल करना भी संभव है, जिसके लिए हैशिंग की अनुमति नहीं है। नीचे दिया गया एल्गोरिदम पहले इनपुट ऐरे को सॉर्ट करता है और फिर सावधानीपूर्वक सभी संभावित जोड़ियों का परीक्षण करता है, जिससे क्रमबद्ध सूची में जोड़ियों के लिए बाइनरी खोज की आवश्यकता से बचा जा सकता है, जिससे सबसे व्यर्थ स्थिति प्राप्त होती है। समय, इस प्रकार है.[8]

सॉर्ट(एस);

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/3 घटाएँ।
  • संशोधित सरणी में, 3 तत्व खोजें जिनका योग 0 है।

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

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

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

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

  • X, Y और Z में प्रत्येक तत्व के लिए, समुच्चय करें: , , .
  • मान लीजिए S, सारणियों X, Y और Z का संयोजन है।
  • तीन तत्वों को खोजने के लिए 3सम×1 ओरेकल का उपयोग करें ऐसा है कि .
  • वापस करना .

जिस तरह से हमने सरणियों को रूपांतरित किया, इसकी गारंटी है aX, bY, cZ.[9]


कनवल्शन योग

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

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


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

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

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

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

  • यदि मूल सारणी में त्रिगुण है , तब , इसलिए यह समाधान 3सम द्वारा T पर पाया जाएगा।
  • इसके विपरीत, यदि नए ऐरे में ट्रिपल विथ है , तब . क्योंकि , अनिवार्य रूप से और , इसलिए यह S पर Conv3सम के लिए वैध समाधान है।

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

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

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

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

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

  • यदि 3सम के लिए कोई समाधान है: , तब: और , इसलिए यह समाधान T पर Conv3सम सॉल्वर द्वारा पाया जाएगा।
  • इसके विपरीत, यदि T पर Conv3सम पाया जाता है, तो जाहिर तौर पर यह S पर 3सम समाधान से मेल खाता है क्योंकि T केवल S का क्रमपरिवर्तन है।

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

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

या

इसके लिए S के तत्वों को T में कॉपी करते समय उनकी नकल करने की आवश्यकता होती है, यानी, प्रत्येक तत्व को रखना होता है में दोनों (पहले की तरह) और अंदर . इसलिए प्रत्येक सेल में 2R तत्व होंगे, और हमें Conv3सम चलाना होगा बार.

3सम-कठोरता

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

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

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


यह भी देखें

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

टिप्पणियाँ

  1. Grønlund & Pettie 2014.
  2. Freund 2017.
  3. Gold & Sharir 2017.
  4. 4.0 4.1 Chan 2018.
  5. Kane, Lovett & Moran 2018.
  6. 6.0 6.1 Kopelowitz, Tsvi; Pettie, Seth; Porat, Ely (2014). "3SUM Hardness in (Dynamic) Data Structures". arXiv:1407.6756 [cs.DS].
  7. Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2009) [1990]. Introduction to Algorithms (3rd ed.). MIT Press and McGraw-Hill. ISBN 0-262-03384-4. Ex. 30.1–7, p. 906.
  8. Visibility Graphs and 3-Sum by Michael Hoffmann
  9. For a reduction in the other direction, see Variants of the 3-sum problem.
  10. 10.0 10.1 10.2 Patrascu, M. (2010). गतिशील समस्याओं के लिए बहुपद निचली सीमा की ओर. Proceedings of the 42nd ACM symposium on Theory of computing - STOC '10. p. 603. doi:10.1145/1806689.1806772. ISBN 9781450300506.
  11. Demaine, Erik; Erickson, Jeff; O'Rourke, Joseph (20 August 2006). "Problem 41: Sorting X + Y (Pairwise Sums)". The Open Problems Project. Retrieved 23 September 2014.


संदर्भ