प्लांटेड क्लिक: Difference between revisions

Latest revision as of 15:46, 12 September 2023

कम्प्यूटेशनल जटिलता सिद्धांत में, एक अप्रत्यक्ष ग्राफ़ में एक प्लांटेड क्लिक या छिपा हुआ क्लिक एक अन्य ग्राफ़ से बना एक क्लिक (ग्राफ़ सिद्धांत) होता है जो शीर्षों के एक उपसमूह का चयन करके और उपसमुच्चय में शीर्षों की प्रत्येक जोड़ी के बीच किनारों को जोड़कर बनता है। प्लांटेड क्लिक समस्या, प्लांटेड क्लिक वाले ग्राफ़ से यादृच्छिक ग्राफ़ को अलग करने की एल्गोरिथम समस्या है। यह क्लिक समस्या का एक रूप है; इसे अर्ध-बहुपद समय में समाधान किया जा सकता है किन्तु अनुमान लगाया गया है कि क्लिक आकार के मध्यवर्ती मानों के लिए यह बहुपद समय में समाधान करने योग्य नहीं है। यह अनुमान कि कोई बहुपद समय समाधान उपस्थित नहीं है, प्लांटेड क्लिक अनुमान कहलाता है; इसका उपयोग कम्प्यूटेशनल कठोरता धारणा के रूप में किया गया है।

परिभाषा

ग्राफ़ में एक क्लिक शीर्षों का एक उपसमूह होता है, जो सभी एक-दूसरे से सटे होते हैं। एक प्लांटेड क्लिक एक चयनित उपसमुच्चय के सभी जोड़े के बीच किनारों को जोड़कर दूसरे ग्राफ से बनाया गया एक क्लिक है।

प्लांटेड क्लिक समस्या को ग्राफ़ पर यादृच्छिक वितरण पर निर्णय समस्या के रूप में औपचारिक रूप दिया जा सकता है, जिसे दो संख्याओं, $n$ (शीर्षों की संख्या), और $k$ (क्लिक का आकार) द्वारा पैरामीटर किया जाता है। इन मापदंडों का उपयोग निम्नलिखित यादृच्छिक प्रक्रिया द्वारा ग्राफ़ उत्पन्न करने के लिए किया जा सकता है:^[1]

शीर्षों के प्रत्येक जोड़े के लिए स्वतंत्र रूप से चयन करके $n$ शीर्षों पर एक एर्दो-रेनी यादृच्छिक ग्राफ़ बनाएं कि क्या प्रत्येक जोड़े के लिए प्रायिकता 1/2 के साथ उस जोड़े को जोड़ने वाला एक किनारा सम्मिलित किया जाए।
प्रायिकता 1/2 के साथ तय करें कि ग्राफ़ में एक क्लिक जोड़ना है या नहीं; यदि नहीं, तो चरण 1 में बनाया गया ग्राफ़ लौटाएँ।
यदि $n$ शीर्ष है तो यादृच्छिक रूप से $k$ का एक उपसमुच्चय चुनें और चयनित शीर्षों के प्रत्येक जोड़े के बीच एक किनारा (यदि कोई पहले से उपस्थित नहीं है) जोड़ें।

समस्या तब एल्गोरिदमिक रूप से यह निर्धारित करने की है कि क्या इस प्रक्रिया से उत्पन्न ग्राफ़ में से एक में कम से कम $k$ शीर्षों का एक समूह है।

ऊपरी और निचली सीमाएं

वहाँ एक फ़ंक्शन $f(n)\sim 2\log _{2}n$ उपस्थित है जैसे कि स्पर्शोन्मुख रूप से लगभग निश्चित रूप से, $n$ -वर्टेक्स यादृच्छिक ग्राफ में सबसे बड़े क्लिक का आकार या तो $f(n)$ या $f(n)+1$ +1 है,^[2] और कुछ स्थिरांक $c$ उपस्थित है जैसे कि आकार के क्लिक्स की अपेक्षित संख्या $\geq f(n)-c$ अनंत में परिवर्तित हो जाता है। परिणामस्वरूप, किसी को अपेक्षा करनी चाहिए कि $\sim 2\log _{2}n$ आकार के एक समूह के रोपण का उच्च संभावना के साथ पता नहीं लगाया जा सकता है।

केंद्रीय सीमा प्रमेय के अनुसार, यादृच्छिक ग्राफ की शीर्ष डिग्री को माध्य ${\frac {n}{2}}$ और मानक विचलन ${\frac {\sqrt {n}}{2}}$ के साथ एक मानक सामान्य वितरण के करीब वितरित किया जाता हैं। परिणामस्वरूप, जब $k$ ${\sqrt {n}}$ के क्रम पर होता है यह वितरण के आकार में एक पता लगाने योग्य परिवर्तन उत्पन्न करता हैं। अर्थात्, यदि आप शीर्ष डिग्री वितरण की योजना बनाते हैं, तो यह एक विकृत घंटी वक्र जैसा दिखेगा। इसलिए, पैरामीटर के लिए मानों की सबसे दिलचस्प श्रेणी $k$ इन दो मानों के बीच है,^[1]

: $2\log _{2}n\ll k\ll {\sqrt {n}}.$

एल्गोरिदम

बड़े क्लिक

पैरामीटर $k$ के पर्याप्त बड़े मानों के लिए, प्लांटेड क्लिक समस्या को बहुपद समय में (उच्च संभावना के साथ) समाधान किया जा सकता है।^[1]

कुचेरा (1995) का मानना है कि, जब $k=\Omega ({\sqrt {n\log n}})$ होता है तो लगभग निश्चित रूप से लगाए गए समूह के सभी शीर्षों की डिग्री समूह के बाहर के सभी शीर्षों की तुलना में अधिक होती है, जिससे समूह को ढूंढना बहुत आसान हो जाता है। वह प्लांटेड क्लिक उदाहरण उत्पन्न करने के लिए यादृच्छिक प्रक्रिया में संशोधन का वर्णन करता है, जो कि $k$ के बड़े मानों के लिए भी शीर्ष डिग्री को अधिक समान बनाता है, किन्तु दिखाता है कि इस संशोधन के अतिरिक्त लगाए गए क्लिक को अभी भी जल्दी से पाया जा सकता है।^[3]

एलोन, क्रिवेलेविच & सुदाकोव (1998) harvtxt error: no target: CITEREFएलोनक्रिवेलेविचसुदाकोव1998 (help) ने सिद्ध किया कि  $k>10{\sqrt {n}}$  एक रोपित क्लिक को निम्नलिखित विधि द्वारा उच्च संभावना के साथ पाया जा सकता है:

आसन्न मैट्रिक्स के आइजन्वेक्टर की गणना उसके दूसरे उच्चतम आइगेनवैल्यूज़ के अनुरूप करें।
उन $k$ शीर्षों का चयन करें जिनके निर्देशांक इसआइजनवेक्टर में सबसे बड़े निरपेक्ष मान हैं।
शीर्षों का वह सेट लौटाएं जो चयनित शीर्षों के कम से कम 3/4 से सटे हों।

वे बताते हैं कि इस विधि को कैसे संशोधित किया जाए जिससे यह कभी भी काम करती रहे $k$ कम से कम शीर्षों की संख्या के वर्गमूल के कुछ गुणज के समानुपाती होता है।^[4] अर्धनिश्चित प्रोग्रामिंग का उपयोग करके बड़े लगाए गए क्लिक्स भी पाए जा सकते हैं।^[5]

यादृच्छिक रूप से नमूनाकरण शीर्षों पर आधारित एक संयोजन विधि $k$ पर समान सीमा प्राप्त कर सकती है और रैखिक समय में चलता है।^[6]

अर्धबहुपद समय

अर्ध-बहुपद समय में, $k$ की पसंद की परवाह किए बिना, प्लांटेड क्लिक समस्या को हल करना भी संभव है।^[7]

क्योंकि यादृच्छिक ग्राफ़ में सबसे बड़े समूह का आकार सामान्यतः $2 log 2 n$ के निकट होता है,^[8] आकार का एक रोपा हुआ समूह $k$ (यदि यह उपस्थित है) निम्न विधि द्वारा उच्च संभावना के साथ पाया जा सकता है:

$\min(k,3\log _{2}n)$ शीर्षों के सभी सेट $S$ के माध्यम से लूप करें।
$S$ की प्रत्येक पसंद के लिए, परीक्षण करें कि क्या $S$ एक गुट है। यदि यह है, और $|S|=k$ , तो $S$ लौटाएँ। अन्यथा, उन शीर्षों का समुच्चय $T$ ज्ञात करें जो $S$ में सभी शीर्षों के निकट हैं। यदि $|T|\geq k$ , तो $T$ लौटाएँ।

इस एल्गोरिदम का चलने का समय अर्धबहुपद है, क्योंकि लूप ओवर करने के लिए $S$ के अर्धबहुपद रूप से कई विकल्प हैं। इस पद्धति से सेट $S$ को आज़माने की गारंटी है जो कि लगाए गए समूह का एक उपसमूह है; उच्च संभावना के साथ सेट $T$ में केवल लगाए गए गुट के अन्य सदस्य सम्मिलित होंगे।

कठोरता धारणा के रूप में

प्लांटेड क्लिक अनुमान यह अनुमान है कि कोई बहुपद समय एल्गोरिथ्म नहीं है जो प्लांटेड क्लिक प्रक्रिया द्वारा उत्पादित इनपुट ग्राफ़ के रूप में लेता है और प्लांटेड क्लिक्स वाले लोगों को उन लोगों से अलग करता है जिनके पास यादृच्छिक मौके की तुलना में अधिक उत्तम संभावना के साथ प्लांटेड क्लिक्स नहीं हैं।^[9]

हज़ान & क्राउथगैमर (2011) ने इस धारणा का उपयोग किया कि लगाए गए क्लिक्स को ढूंढना एक कम्प्यूटेशनल कठोरता धारणा के रूप में कठिन है, यह साबित करने के लिए कि यदि ऐसा है, तो दो-खिलाड़ियों के खेल में सर्वोत्तम नैश संतुलन का अनुमान लगाना भी कठिन है।^[7] सामाजिक नेटवर्क^[10] और यंत्र अधिगम^[11] में क्लस्टर खोजने वाले यादृच्छिक वितरण की संपत्ति परीक्षण $k$ -यादृच्छिक वितरण की स्वतंत्रता,^[12] की कठिनाई को दिखाने के लिए प्लांटेड क्लिक अनुमान का उपयोग कठोरता धारणा के रूप में भी किया गया है।

संदर्भ

↑ ^1.0 ^1.1 ^1.2 Arora, Sanjeev; Barak, Boaz (2009), Computational Complexity: A Modern Approach, Cambridge University Press, pp. 362–363, ISBN 9780521424264.
↑ Bollobas, B.; Erdös, P. (November 1976). "यादृच्छिक ग्राफ़ में क्लिक्स". Mathematical Proceedings of the Cambridge Philosophical Society (in English). 80 (3): 419–427. doi:10.1017/S0305004100053056. ISSN 1469-8064. S2CID 16619643.
↑ Kučera, Luděk (1995), "Expected complexity of graph partitioning problems", Discrete Applied Mathematics, 57 (2–3): 193–212, doi:10.1016/0166-218X(94)00103-K, hdl:11858/00-001M-0000-0014-B73F-2, MR 1327775.
↑ Alon, Noga; Krivelevich, Michael; Sudakov, Benny (1998), "Finding a large hidden clique in a random graph", Random Structures & Algorithms, 13 (3–4): 457–466, CiteSeerX 10.1.1.24.6419, doi:10.1002/(SICI)1098-2418(199810/12)13:3/4<457::AID-RSA14>3.3.CO;2-K, MR 1662795
↑ Feige, U.; Krauthgamer, R. (2000), "Finding and certifying a large hidden clique in a semirandom graph", Random Structures and Algorithms, 16 (2): 195–208, doi:10.1002/(SICI)1098-2418(200003)16:2<195::AID-RSA5>3.0.CO;2-A.
↑ Dekel, Yael; Gurel-Gurevich, Ori; Peres, Yuval (2014), "Finding hidden cliques in linear time with high probability", Combinatorics, Probability and Computing, 23 (1): 29–49, arXiv:1010.2997, doi:10.1017/S096354831300045X, MR 3197965, S2CID 14356678.
↑ ^7.0 ^7.1 Hazan, Elad; Krauthgamer, Robert (2011), "How hard is it to approximate the best Nash equilibrium?", SIAM Journal on Computing, 40 (1): 79–91, CiteSeerX 10.1.1.511.4422, doi:10.1137/090766991, MR 2765712.
↑ Grimmett, G. R.; McDiarmid, C. J. H. (1975), "On colouring random graphs", Mathematical Proceedings of the Cambridge Philosophical Society, 77 (2): 313–324, Bibcode:1975MPCPS..77..313G, doi:10.1017/S0305004100051124, MR 0369129, S2CID 3421302.
↑ Braverman, Mark; Ko, Young Kun; Rubinstein, Aviad; Weinstein, Omri (2015), ETH hardness for densest- $k$ -subgraph with perfect completeness, arXiv:1504.08352, Bibcode:2015arXiv150408352B.
↑ Balcan, Maria-Florina; Borgs, Christian; Braverman, Mark; Chayes, Jennifer; Teng, Shang-Hua (2013), "Finding Endogenously Formed Communities", Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA '13), SIAM, pp. 767–783, ISBN 978-1-611972-51-1.
↑ Berthet, Quentin; Rigollet, Philippe (2013), "Complexity theoretic lower bounds for sparse principal component detection", Conference on Learning Theory, Journal of Machine Learning Research, 30: 1046–1066.
↑ Alon, Noga; Andoni, Alexandr; Kaufman, Tali; Matulef, Kevin; Rubinfeld, Ronitt; Xie, Ning (2007), "Testing $k$ -wise and almost $k$ -wise independence", STOC'07—Proceedings of the 39th Annual ACM Symposium on Theory of Computing, New York: ACM, pp. 496–505, doi:10.1145/1250790.1250863, ISBN 9781595936318, MR 2402475, S2CID 5050980.

[ab-1] 1.0 ^1.1 ^1.2 Arora, Sanjeev; Barak, Boaz (2009), Computational Complexity: A Modern Approach, Cambridge University Press, pp. 362–363, ISBN 9780521424264.

[2] Bollobas, B.; Erdös, P. (November 1976). "यादृच्छिक ग्राफ़ में क्लिक्स". Mathematical Proceedings of the Cambridge Philosophical Society (in English). 80 (3): 419–427. doi:10.1017/S0305004100053056. ISSN 1469-8064. S2CID 16619643.

[3] Kučera, Luděk (1995), "Expected complexity of graph partitioning problems", Discrete Applied Mathematics, 57 (2–3): 193–212, doi:10.1016/0166-218X(94)00103-K, hdl:11858/00-001M-0000-0014-B73F-2, MR 1327775.

[4] Alon, Noga; Krivelevich, Michael; Sudakov, Benny (1998), "Finding a large hidden clique in a random graph", Random Structures & Algorithms, 13 (3–4): 457–466, CiteSeerX 10.1.1.24.6419, doi:10.1002/(SICI)1098-2418(199810/12)13:3/4<457::AID-RSA14>3.3.CO;2-K, MR 1662795

[5] Feige, U.; Krauthgamer, R. (2000), "Finding and certifying a large hidden clique in a semirandom graph", Random Structures and Algorithms, 16 (2): 195–208, doi:10.1002/(SICI)1098-2418(200003)16:2<195::AID-RSA5>3.0.CO;2-A.

[6] Dekel, Yael; Gurel-Gurevich, Ori; Peres, Yuval (2014), "Finding hidden cliques in linear time with high probability", Combinatorics, Probability and Computing, 23 (1): 29–49, arXiv:1010.2997, doi:10.1017/S096354831300045X, MR 3197965, S2CID 14356678.

[hk-7] 7.0 ^7.1 Hazan, Elad; Krauthgamer, Robert (2011), "How hard is it to approximate the best Nash equilibrium?", SIAM Journal on Computing, 40 (1): 79–91, CiteSeerX 10.1.1.511.4422, doi:10.1137/090766991, MR 2765712.

[8] Grimmett, G. R.; McDiarmid, C. J. H. (1975), "On colouring random graphs", Mathematical Proceedings of the Cambridge Philosophical Society, 77 (2): 313–324, Bibcode:1975MPCPS..77..313G, doi:10.1017/S0305004100051124, MR 0369129, S2CID 3421302.

[9] Braverman, Mark; Ko, Young Kun; Rubinstein, Aviad; Weinstein, Omri (2015), ETH hardness for densest- $k$ -subgraph with perfect completeness, arXiv:1504.08352, Bibcode:2015arXiv150408352B.

[10] Balcan, Maria-Florina; Borgs, Christian; Braverman, Mark; Chayes, Jennifer; Teng, Shang-Hua (2013), "Finding Endogenously Formed Communities", Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA '13), SIAM, pp. 767–783, ISBN 978-1-611972-51-1.

[11] Berthet, Quentin; Rigollet, Philippe (2013), "Complexity theoretic lower bounds for sparse principal component detection", Conference on Learning Theory, Journal of Machine Learning Research, 30: 1046–1066.

[12] Alon, Noga; Andoni, Alexandr; Kaufman, Tali; Matulef, Kevin; Rubinfeld, Ronitt; Xie, Ning (2007), "Testing $k$ -wise and almost $k$ -wise independence", STOC'07—Proceedings of the 39th Annual ACM Symposium on Theory of Computing, New York: ACM, pp. 496–505, doi:10.1145/1250790.1250863, ISBN 9781595936318, MR 2402475, S2CID 5050980.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

@@ Line 1: / Line 1: @@
 {{Short description|Complete subgraph added to a random graph}}
-[[कम्प्यूटेशनल जटिलता सिद्धांत]] में, एक [[अप्रत्यक्ष ग्राफ]]़ में एक प्लांटेड क्लिक या छिपा हुआ क्लिक एक क्लिक (ग्राफ़ सिद्धांत) होता है जो दूसरे ग्राफ़ से शीर्षों के एक उपसमूह का चयन करके और उपसमुच्चय में शीर्षों की प्रत्येक जोड़ी के बीच किनारों को जोड़कर बनाया जाता है। प्लांटेड क्लिक समस्या, प्लांटेड क्लिक वाले ग्राफ़ से [[यादृच्छिक ग्राफ]]़ को अलग करने की एल्गोरिथम समस्या है। यह गुट समस्या का एक रूप है; इसे [[अर्ध-बहुपद समय]] में हल किया जा सकता है लेकिन अनुमान लगाया गया है कि क्लिक आकार के मध्यवर्ती मूल्यों के लिए यह बहुपद समय में हल करने योग्य नहीं है। यह अनुमान कि कोई बहुपद समय समाधान मौजूद नहीं है, प्लांटेड क्लिक अनुमान कहलाता है; इसका उपयोग [[कम्प्यूटेशनल कठोरता धारणा]] के रूप में किया गया है।
+[[कम्प्यूटेशनल जटिलता सिद्धांत]] में, एक [[अप्रत्यक्ष ग्राफ|अप्रत्यक्ष ग्राफ़]] में एक प्लांटेड क्लिक या छिपा हुआ क्लिक एक अन्य ग्राफ़ से बना एक क्लिक (ग्राफ़ सिद्धांत) होता है जो शीर्षों के एक उपसमूह का चयन करके और उपसमुच्चय में शीर्षों की प्रत्येक जोड़ी के बीच किनारों को जोड़कर बनता है। प्लांटेड क्लिक समस्या, प्लांटेड क्लिक वाले ग्राफ़ से [[यादृच्छिक ग्राफ|यादृच्छिक ग्राफ़]] को अलग करने की एल्गोरिथम समस्या है। यह क्लिक समस्या का एक रूप है; इसे [[अर्ध-बहुपद समय]] में समाधान किया जा सकता है किन्तु अनुमान लगाया गया है कि क्लिक आकार के मध्यवर्ती मानों के लिए यह बहुपद समय में समाधान करने योग्य नहीं है। यह अनुमान कि कोई बहुपद समय समाधान उपस्थित नहीं है, प्लांटेड क्लिक अनुमान कहलाता है; इसका उपयोग [[कम्प्यूटेशनल कठोरता धारणा]] के रूप में किया गया है।
 ==परिभाषा==
 ग्राफ़ में एक क्लिक शीर्षों का एक उपसमूह होता है, जो सभी एक-दूसरे से सटे होते हैं। एक प्लांटेड क्लिक एक चयनित उपसमुच्चय के सभी जोड़े के बीच किनारों को जोड़कर दूसरे ग्राफ से बनाया गया एक क्लिक है।
-प्लांटेड क्लिक समस्या को दो संख्याओं द्वारा मानकीकृत, ग्राफ़ पर [[यादृच्छिक वितरण]] पर [[निर्णय समस्या]] के रूप में औपचारिक रूप दिया जा सकता है, {{mvar|n}} (शीर्षों की संख्या), और {{mvar|k}} (गुट का आकार).
+प्लांटेड क्लिक समस्या को ग्राफ़ पर [[यादृच्छिक वितरण]] पर [[निर्णय समस्या]] के रूप में औपचारिक रूप दिया जा सकता है, जिसे दो संख्याओं, {{mvar|n}} (शीर्षों की संख्या), और {{mvar|k}} (क्लिक का आकार) द्वारा पैरामीटर किया जाता है। इन मापदंडों का उपयोग निम्नलिखित यादृच्छिक प्रक्रिया द्वारा ग्राफ़ उत्पन्न करने के लिए किया जा सकता है:<ref name="ab">{{citation|title=Computational Complexity: A Modern Approach|first1=Sanjeev|last1=Arora|author1-link=Sanjeev Arora|first2=Boaz|last2=Barak|publisher=Cambridge University Press|year=2009|isbn=9780521424264|pages=362–363|url=https://books.google.com/books?id=8Wjqvsoo48MC&pg=PA362}}.</ref>
-इन मापदंडों का उपयोग निम्नलिखित यादृच्छिक प्रक्रिया द्वारा ग्राफ़ उत्पन्न करने के लिए किया जा सकता है:<ref name="ab">{{citation|title=Computational Complexity: A Modern Approach|first1=Sanjeev|last1=Arora|author1-link=Sanjeev Arora|first2=Boaz|last2=Barak|publisher=Cambridge University Press|year=2009|isbn=9780521424264|pages=362–363|url=https://books.google.com/books?id=8Wjqvsoo48MC&pg=PA362}}.</ref>
+#शीर्षों के प्रत्येक जोड़े के लिए स्वतंत्र रूप से चयन करके {{mvar|n}} शीर्षों पर एक एर्दो-रेनी यादृच्छिक ग्राफ़ बनाएं कि क्या प्रत्येक जोड़े के लिए प्रायिकता 1/2 के साथ उस जोड़े को जोड़ने वाला एक किनारा सम्मिलित किया जाए।
-#Erdős-Rényi मॉडल बनाएं|Erdős-Rényi यादृच्छिक ग्राफ़ पर {{mvar|n}} शीर्षों के प्रत्येक जोड़े के लिए स्वतंत्र रूप से चयन करके कि क्या उस जोड़े को जोड़ने वाले किनारे को शामिल किया जाए, प्रत्येक जोड़े के लिए प्रायिकता 1/2 के साथ।
 #प्रायिकता 1/2 के साथ तय करें कि ग्राफ़ में एक क्लिक जोड़ना है या नहीं; यदि नहीं, तो चरण 1 में बनाया गया ग्राफ़ लौटाएँ।
-#बेतरतीब ढंग से एक उपसमूह चुनें {{mvar|k}} की {{mvar|n}} शीर्ष और चयनित शीर्षों के प्रत्येक जोड़े के बीच एक किनारा जोड़ें (यदि कोई पहले से मौजूद नहीं है)।
+#यदि {{mvar|n}} शीर्ष है तो यादृच्छिक रूप से {{mvar|k}} का एक उपसमुच्चय चुनें और चयनित शीर्षों के प्रत्येक जोड़े के बीच एक किनारा (यदि कोई पहले से उपस्थित नहीं है) जोड़ें।
-समस्या तब एल्गोरिदमिक रूप से यह निर्धारित करने की है कि क्या इस प्रक्रिया से उत्पन्न ग्राफ़ में से किसी एक में कम से कम एक समूह है {{mvar|k}} शिखर.
+समस्या तब एल्गोरिदमिक रूप से यह निर्धारित करने की है कि क्या इस प्रक्रिया से उत्पन्न ग्राफ़ में से एक में कम से कम {{mvar|k}} शीर्षों का एक समूह है।
 === ऊपरी और निचली सीमाएं ===
-वहाँ एक फ़ंक्शन मौजूद है <math>f(n) \sim 2 \log_2 n</math> इस तरह कि स्पर्शोन्मुख रूप से लगभग निश्चित रूप से, एक में सबसे बड़े गुट का आकार {{mvar|n}}-वर्टेक्स रैंडम ग्राफ या तो है <math>f(n)</math> या <math>f(n)+1</math>,<ref>{{Cite journal |last1=Bollobas |first1=B. |last2=Erdös |first2=P. |date=November 1976 |title=यादृच्छिक ग्राफ़ में क्लिक्स|url=https://www.cambridge.org/core/journals/mathematical-proceedings-of-the-cambridge-philosophical-society/article/abs/cliques-in-random-graphs/27321102B82EDEEF362556BE714FACD9 |journal=Mathematical Proceedings of the Cambridge Philosophical Society |language=en |volume=80 |issue=3 |pages=419–427 |doi=10.1017/S0305004100053056 |s2cid=16619643 |issn=1469-8064}}</ref> और वहां कुछ स्थिरांक मौजूद है <math>c</math> इस प्रकार कि आकार के क्लिक्स की अपेक्षित संख्या <math>\geq f(n) -c</math> अनन्त में परिवर्तित हो जाता है। नतीजतन, किसी को उम्मीद करनी चाहिए कि रोपण एक समूह के आकार का होगा <math>\sim 2 \log_2 n</math> उच्च संभावना के साथ पता नहीं लगाया जा सकता।
+वहाँ एक फ़ंक्शन <math>f(n) \sim 2 \log_2 n</math> उपस्थित है जैसे कि स्पर्शोन्मुख रूप से लगभग निश्चित रूप से, {{mvar|n}}-वर्टेक्स यादृच्छिक ग्राफ में सबसे बड़े क्लिक का आकार या तो <math>f(n)</math> या <math>f(n)+1</math>+1 है,<ref>{{Cite journal |last1=Bollobas |first1=B. |last2=Erdös |first2=P. |date=November 1976 |title=यादृच्छिक ग्राफ़ में क्लिक्स|url=https://www.cambridge.org/core/journals/mathematical-proceedings-of-the-cambridge-philosophical-society/article/abs/cliques-in-random-graphs/27321102B82EDEEF362556BE714FACD9 |journal=Mathematical Proceedings of the Cambridge Philosophical Society |language=en |volume=80 |issue=3 |pages=419–427 |doi=10.1017/S0305004100053056 |s2cid=16619643 |issn=1469-8064}}</ref> और कुछ स्थिरांक <math>c</math> उपस्थित है जैसे कि आकार के क्लिक्स की अपेक्षित संख्या <math>\geq f(n) -c</math> अनंत में परिवर्तित हो जाता है। परिणामस्वरूप, किसी को अपेक्षा करनी चाहिए कि <math>\sim 2 \log_2 n</math> आकार के एक समूह के रोपण का उच्च संभावना के साथ पता नहीं लगाया जा सकता है।
+[[केंद्रीय सीमा प्रमेय]] के अनुसार, यादृच्छिक ग्राफ की शीर्ष डिग्री को माध्य <math>\frac n2</math> और मानक विचलन <math>\frac \sqrt{n} 2</math> के साथ एक मानक सामान्य वितरण के करीब वितरित किया जाता हैं। परिणामस्वरूप, जब <math>k</math> <math>\sqrt n</math> के क्रम पर होता है  यह वितरण के आकार में एक पता लगाने योग्य परिवर्तन उत्पन्न करता हैं। अर्थात्, यदि आप शीर्ष डिग्री वितरण की योजना बनाते हैं, तो यह एक विकृत घंटी वक्र जैसा दिखेगा। इसलिए, पैरामीटर के लिए मानों की सबसे दिलचस्प श्रेणी {{mvar|k}} इन दो मानों के बीच है,<ref name="ab" />
+<nowiki>:</nowiki><math>2\log_2 n \ll k \ll \sqrt n.</math>
-[[केंद्रीय सीमा प्रमेय]] के अनुसार, यादृच्छिक ग्राफ की शीर्ष डिग्री को माध्य के साथ एक मानक सामान्य वितरण के करीब वितरित किया जाएगा <math>\frac n2</math> और मानक विचलन <math>\frac \sqrt{n} 2</math>. नतीजतन, जब <math>k</math> के आदेश पर है <math>\sqrt n</math> यह वितरण के आकार में एक पता लगाने योग्य परिवर्तन पैदा करेगा। अर्थात्, यदि आप शीर्ष डिग्री वितरण की योजना बनाते हैं, तो यह एक विकृत घंटी वक्र जैसा दिखेगा। इसलिए, पैरामीटर के लिए मानों की सबसे दिलचस्प श्रेणी {{mvar|k}} इन दो मानों के बीच है,<ref name="ab" />:<math>2\log_2 n \ll k \ll \sqrt n.</math>
 ==एल्गोरिदम==
-===बड़े गुट===
+===बड़े क्लिक===
-पैरामीटर के पर्याप्त बड़े मानों के लिए {{mvar|k}}, प्लांटेड क्लिक समस्या को बहुपद समय में (उच्च संभावना के साथ) हल किया जा सकता है।<ref name="ab"/>
+पैरामीटर {{mvar|k}} के पर्याप्त बड़े मानों के लिए, प्लांटेड क्लिक समस्या को बहुपद समय में (उच्च संभावना के साथ) समाधान किया जा सकता है।<ref name="ab"/>
-{{harvtxt|Kučera|1995}} देखता है कि, कब <math>k=\Omega(\sqrt{n\log n})</math> तो लगभग निश्चित रूप से लगाए गए समूह के सभी शीर्षों में समूह के बाहर के सभी शीर्षों की तुलना में उच्च डिग्री होती है, जिससे समूह को ढूंढना बहुत आसान हो जाता है। वह प्लांटेड क्लिक उदाहरण उत्पन्न करने के लिए यादृच्छिक प्रक्रिया में संशोधन का वर्णन करता है, जो बड़े मूल्यों के लिए भी शीर्ष डिग्री को अधिक समान बनाता है{{mvar|k}}, लेकिन दिखाता है कि इस संशोधन के बावजूद लगाए गए क्लिक को अभी भी जल्दी से पाया जा सकता है।<ref>{{citation
+{{harvtxt|कुचेरा|1995}} का मानना है कि, जब <math>k=\Omega(\sqrt{n\log n})</math> होता है तो लगभग निश्चित रूप से लगाए गए समूह के सभी शीर्षों की डिग्री समूह के बाहर के सभी शीर्षों की तुलना में अधिक होती है, जिससे समूह को ढूंढना बहुत आसान हो जाता है। वह प्लांटेड क्लिक उदाहरण उत्पन्न करने के लिए यादृच्छिक प्रक्रिया में संशोधन का वर्णन करता है, जो कि {{mvar|k}} के बड़े मानों के लिए भी शीर्ष डिग्री को अधिक समान बनाता है, किन्तु दिखाता है कि इस संशोधन के अतिरिक्त लगाए गए क्लिक को अभी भी जल्दी से पाया जा सकता है।<ref>{{citation
   | last = Kučera | first = Luděk
   | doi = 10.1016/0166-218X(94)00103-K
@@ Line 36: / Line 38: @@
   }}.</ref>
-  {{harvtxt|Alon|Krivelevich|Sudakov|1998}} के लिए सिद्ध करें <math>k>10\sqrt n</math> एक रोपित गुट को निम्नलिखित विधि द्वारा उच्च संभावना के साथ पाया जा सकता है:
+  {{harvtxt|एलोन|क्रिवेलेविच|सुदाकोव|1998}} ने सिद्ध किया कि <math>k>10\sqrt n</math> एक रोपित क्लिक को निम्नलिखित विधि द्वारा उच्च संभावना के साथ पाया जा सकता है:
-#आसन्न मैट्रिक्स के [[eigenvector]] की गणना उसके दूसरे उच्चतम [[eigenvalue]] के अनुरूप करें।
+#आसन्न मैट्रिक्स के [[eigenvector|आइजन्वेक्टर]] की गणना उसके दूसरे उच्चतम [[eigenvalue|आइगेनवैल्यूज़]] के अनुरूप करें।
-#का चयन करें {{mvar|k}} शीर्ष जिनके निर्देशांक इस आइजनवेक्टर में सबसे बड़े निरपेक्ष मान हैं।
+#उन {{mvar|k}} शीर्षों का चयन करें जिनके निर्देशांक इसआइजनवेक्टर में सबसे बड़े निरपेक्ष मान हैं।
 #शीर्षों का वह सेट लौटाएं जो चयनित शीर्षों के कम से कम 3/4 से सटे हों।
-वे बताते हैं कि इस तकनीक को कैसे संशोधित किया जाए ताकि यह कभी भी काम करती रहे {{mvar|k}} कम से कम शीर्षों की संख्या के वर्गमूल के कुछ गुणज के समानुपाती होता है।<ref>{{citation
+वे बताते हैं कि इस विधि को कैसे संशोधित किया जाए जिससे यह कभी भी काम करती रहे {{mvar|k}} कम से कम शीर्षों की संख्या के वर्गमूल के कुछ गुणज के समानुपाती होता है।<ref>{{citation
   | last1 = Alon | first1 = Noga | author1-link = Noga Alon
   | last2 = Krivelevich | first2 = Michael | author2-link = Michael Krivelevich
@@ Line 52: / Line 54: @@
   | volume = 13
   | year = 1998| citeseerx = 10.1.1.24.6419 }}</ref> [[अर्धनिश्चित प्रोग्रामिंग]] का उपयोग करके बड़े लगाए गए क्लिक्स भी पाए जा सकते हैं।<ref>{{citation |first1=U. |last1=Feige |author1-link=Uriel Feige |first2=R. |last2=Krauthgamer |title=Finding and certifying a large hidden clique in a semirandom graph |journal=Random Structures and Algorithms |volume=16 |issue=2 |pages=195–208 |year=2000 |doi=10.1002/(SICI)1098-2418(200003)16:2<195::AID-RSA5>3.0.CO;2-A}}.</ref>
-बेतरतीब ढंग से नमूनाकरण शीर्षों पर आधारित एक संयोजन तकनीक उसी सीमा को प्राप्त कर सकती है {{mvar|k}} और [[रैखिक समय]] में चलता है।<ref>{{citation
+यादृच्छिक रूप से नमूनाकरण शीर्षों पर आधारित एक संयोजन विधि {{mvar|k}} पर समान सीमा प्राप्त कर सकती है और [[रैखिक समय]] में चलता है।<ref>{{citation
   | last1 = Dekel | first1 = Yael
   | last2 = Gurel-Gurevich | first2 = Ori
@@ Line 66: / Line 69: @@
   | year = 2014| s2cid = 14356678
   }}.</ref>
 ===अर्धबहुपद समय===
-पसंद की परवाह किए बिना, प्लांटेड क्लिक समस्या को हल करना भी संभव है {{mvar|k}}, अर्ध-बहुपद समय में।<ref name="hk">{{citation
+अर्ध-बहुपद समय में, {{mvar|k}} की पसंद की परवाह किए बिना, प्लांटेड क्लिक समस्या को हल करना भी संभव है।<ref name="hk">{{citation
   | last1 = Hazan | first1 = Elad
   | last2 = Krauthgamer | first2 = Robert
@@ Line 81: / Line 85: @@
   | year = 2011| citeseerx = 10.1.1.511.4422
   }}.</ref>
-क्योंकि यादृच्छिक ग्राफ़ में सबसे बड़े समूह का आकार आम तौर पर निकट होता है {{math|2 log<sub>2</sub> ''n''}},<ref>{{citation
+क्योंकि यादृच्छिक ग्राफ़ में सबसे बड़े समूह का आकार सामान्यतः {{math|2 log<sub>2</sub> ''n''}} के निकट होता है,<ref>{{citation
   | last1 = Grimmett | first1 = G. R. | author1-link = Geoffrey Grimmett
   | last2 = McDiarmid | first2 = C. J. H.
@@ Line 90: / Line 95: @@
   | title = On colouring random graphs
   | volume = 77
-  | issue = 2 | year = 1975| bibcode = 1975MPCPS..77..313G| s2cid = 3421302 }}.</ref> आकार का एक रोपा हुआ समूह {{mvar|k}} (यदि यह मौजूद है) निम्न विधि द्वारा उच्च संभावना के साथ पाया जा सकता है:
+  | issue = 2 | year = 1975| bibcode = 1975MPCPS..77..313G| s2cid = 3421302 }}.</ref> आकार का एक रोपा हुआ समूह {{mvar|k}} (यदि यह उपस्थित है) निम्न विधि द्वारा उच्च संभावना के साथ पाया जा सकता है:
-#सभी सेटों के माध्यम से लूप करें {{mvar|S}} का <math>\min(k,3\log_2 n)</math> शिखर.
+#<math>\min(k,3\log_2 n)</math> शीर्षों के सभी सेट {{mvar|S}} के माध्यम से लूप करें।
-#प्रत्येक विकल्प के लिए {{mvar|S}}, परीक्षण करें कि क्या {{mvar|S}} एक गुट है. यदि यह है, और <math>|S| = k</math>, वापस करना {{mvar|S}}. अन्यथा, सेट ढूंढें {{mvar|T}} उन शीर्षों का जो सभी शीर्षों से सटे हुए हैं {{mvar|S}}. अगर <math>|T|\ge k</math>, वापस करना {{mvar|T}}.
+#{{mvar|S}} की प्रत्येक पसंद के लिए, परीक्षण करें कि क्या {{mvar|S}} एक गुट है। यदि यह है, और <math>|S| = k</math>, तो {{mvar|S}} लौटाएँ। अन्यथा, उन शीर्षों का समुच्चय {{mvar|T}} ज्ञात करें जो {{mvar|S}} में सभी शीर्षों के निकट हैं। यदि <math>|T|\ge k</math>, तो {{mvar|T}} लौटाएँ।
-इस एल्गोरिथ्म का चलने का समय अर्धबहुपद है, क्योंकि अर्धबहुपद के कई विकल्प हैं {{mvar|S}} लूप ओवर करना। यह विधि एक सेट को आज़माने की गारंटी है {{mvar|S}} वह रोपित गुट का एक उपसमुच्चय है; उच्च संभावना के साथ, सेट {{mvar|T}} में केवल लगाए गए गुट के अन्य सदस्य शामिल होंगे।
+इस एल्गोरिदम का चलने का समय अर्धबहुपद है, क्योंकि लूप ओवर करने के लिए {{mvar|S}} के अर्धबहुपद रूप से कई विकल्प हैं। इस पद्धति से सेट {{mvar|S}} को आज़माने की गारंटी है जो कि लगाए गए समूह का एक उपसमूह है; उच्च संभावना के साथ सेट {{mvar|T}} में केवल लगाए गए गुट के अन्य सदस्य सम्मिलित होंगे।
 ==कठोरता धारणा के रूप में==
-प्लांटेड क्लिक अनुमान यह अनुमान है कि कोई बहुपद समय एल्गोरिथ्म नहीं है जो प्लांटेड क्लिक प्रक्रिया द्वारा उत्पादित इनपुट ग्राफ़ के रूप में लेता है और प्लांटेड क्लिक्स वाले लोगों को उन लोगों से अलग करता है जिनके पास यादृच्छिक मौके की तुलना में काफी बेहतर संभावना के साथ प्लांटेड क्लिक्स नहीं हैं।<ref>{{citation
+प्लांटेड क्लिक अनुमान यह अनुमान है कि कोई बहुपद समय एल्गोरिथ्म नहीं है जो प्लांटेड क्लिक प्रक्रिया द्वारा उत्पादित इनपुट ग्राफ़ के रूप में लेता है और प्लांटेड क्लिक्स वाले लोगों को उन लोगों से अलग करता है जिनके पास यादृच्छिक मौके की तुलना में अधिक उत्तम संभावना के साथ प्लांटेड क्लिक्स नहीं हैं।<ref>{{citation
   | last1 = Braverman | first1 = Mark
   | last2 = Ko | first2 = Young Kun
@@ Line 105: / Line 110: @@
   | year = 2015| bibcode = 2015arXiv150408352B}}.</ref>
-{{harvtxt|Hazan|Krauthgamer|2011}} ने इस धारणा का उपयोग किया कि प्लांटेड क्लिक्स को ढूंढना एक कम्प्यूटेशनल कठोरता धारणा के रूप में कठिन है, यह साबित करने के लिए कि यदि ऐसा है, तो दो-खिलाड़ियों के खेल में सर्वोत्तम [[नैश संतुलन]] का अनुमान लगाना भी कठिन है।<ref name="hk"/>[[संपत्ति परीक्षण]] के-स्वतंत्र हैशिंग की कठिनाई को दिखाने के लिए प्लांटेड क्लिक अनुमान का उपयोग कठोरता धारणा के रूप में भी किया गया है |{{mvar|k}}-यादृच्छिक वितरण की स्वतंत्रता,<ref>{{citation
+{{harvtxt|हज़ान |क्राउथगैमर|2011}} ने इस धारणा का उपयोग किया कि लगाए गए क्लिक्स को ढूंढना एक कम्प्यूटेशनल कठोरता धारणा के रूप में कठिन है, यह साबित करने के लिए कि यदि ऐसा है, तो दो-खिलाड़ियों के खेल में सर्वोत्तम [[नैश संतुलन]] का अनुमान लगाना भी कठिन है।<ref name="hk"/> सामाजिक नेटवर्क<ref>{{citation
- | last1 = Alon | first1 = Noga | author1-link = Noga Alon
- | last2 = Andoni | first2 = Alexandr
- | last3 = Kaufman | first3 = Tali
- | last4 = Matulef | first4 = Kevin
- | last5 = Rubinfeld | first5 = Ronitt
- | last6 = Xie | first6 = Ning
- | contribution = Testing {{mvar|k}}-wise and almost {{mvar|k}}-wise independence
- | doi = 10.1145/1250790.1250863
- | mr = 2402475
- | pages = 496–505
- | publisher = ACM | location = New York
- | title = STOC'07—Proceedings of the 39th Annual ACM Symposium on Theory of Computing
- | year = 2007| isbn = 9781595936318 | s2cid = 5050980 }}.</ref> सामाजिक नेटवर्क में क्लस्टर ढूँढना,<ref>{{citation
   | last1 = Balcan | first1 = Maria-Florina | author1-link = Maria-Florina Balcan
   | last2 = Borgs | first2 = Christian
@@ Line 130: / Line 122: @@
   | publisher = SIAM
   | title = Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA '13)
-  | year = 2013}}.</ref> और [[ यंत्र अधिगम ]]।<ref>{{citation
+  | year = 2013}}.</ref> और [[ यंत्र अधिगम |यंत्र अधिगम]]<ref>{{citation
   | last1 = Berthet | first1 = Quentin
   | last2 = Rigollet | first2 = Philippe
@@ Line 139: / Line 131: @@
   | url = http://jmlr.org/proceedings/papers/v30/Berthet13.html
   | volume = 30
-  | year = 2013}}.</ref>
+  | year = 2013}}.</ref> में क्लस्टर खोजने वाले यादृच्छिक वितरण की [[संपत्ति परीक्षण]] {{mvar|k}}-यादृच्छिक वितरण की स्वतंत्रता,<ref>{{citation
+ | last1 = Alon | first1 = Noga | author1-link = Noga Alon
+ | last2 = Andoni | first2 = Alexandr
+ | last3 = Kaufman | first3 = Tali
+ | last4 = Matulef | first4 = Kevin
+ | last5 = Rubinfeld | first5 = Ronitt
+ | last6 = Xie | first6 = Ning
+ | contribution = Testing {{mvar|k}}-wise and almost {{mvar|k}}-wise independence
+ | doi = 10.1145/1250790.1250863
+ | mr = 2402475
+ | pages = 496–505
+ | publisher = ACM | location = New York
+ | title = STOC'07—Proceedings of the 39th Annual ACM Symposium on Theory of Computing
+ | year = 2007| isbn = 9781595936318 | s2cid = 5050980 }}.</ref>  की कठिनाई को दिखाने के लिए प्लांटेड क्लिक अनुमान का उपयोग कठोरता धारणा के रूप में भी किया गया है।
@@ Line 146: / Line 152: @@
 {{Computational hardness assumptions}}
-[[Category: ग्राफ सिद्धांत में कम्प्यूटेशनल समस्याएं]] [[Category: कम्प्यूटेशनल कठोरता धारणाएँ]]
-[[Category: Machine Translated Page]]
+[[Category:CS1 English-language sources (en)]]
+[[Category:Collapse templates]]
 [[Category:Created On 27/06/2023]]
+[[Category:Lua-based templates]]
+[[Category:Machine Translated Page]]
+[[Category:Navigational boxes| ]]
+[[Category:Navigational boxes without horizontal lists]]
+[[Category:Pages with script errors]]
+[[Category:Sidebars with styles needing conversion]]
+[[Category:Template documentation pages|Documentation/doc]]
+[[Category:Templates Translated in Hindi]]
+[[Category:Templates Vigyan Ready]]
+[[Category:Templates generating microformats]]
+[[Category:Templates that add a tracking category]]
+[[Category:Templates that are not mobile friendly]]
+[[Category:Templates that generate short descriptions]]
+[[Category:Templates using TemplateData]]
+[[Category:Wikipedia metatemplates]]
+[[Category:कम्प्यूटेशनल कठोरता धारणाएँ]]
+[[Category:ग्राफ सिद्धांत में कम्प्यूटेशनल समस्याएं]]

v t e कम्प्यूटेशनल कठोरता धारणाएं
संख्या सिद्धांत	पूर्णांक कारक फी-छिपा आरएसए समस्या मजबूत आरएसए द्विघात अवशेष निर्णायक समग्र अवशेष उच्च अवशेष
समूह सिद्धांत	असतत लॉगरिथम डिफी-हेलमैन निर्णायक डिफी -हेलमैन कम्प्यूटेशनल डिफी -हेलमैन
जोड़ियां	बाहरी diffie -hellman उप-समूह छिपा हुआ निर्णय रैखिक
जाली	सबसे छोटा वेक्टर समस्या निकटतम वेक्टर समस्या ( GAP त्रुटियों के साथ सीखना त्रुटियों के साथ रिंग सीखना लघु पूर्णांक समाधान
गैर-क्रिप्टोग्राफ़िक	घातीय समय परिकल्पना अद्वितीय खेल अनुमान लगाए गए क्लिक कॉनजेक्चर

Anonymous

Search

प्लांटेड क्लिक: Difference between revisions

Namespaces

More

Page actions

Latest revision as of 15:46, 12 September 2023

Contents

परिभाषा

ऊपरी और निचली सीमाएं

एल्गोरिदम

बड़े क्लिक

अर्धबहुपद समय

कठोरता धारणा के रूप में

संदर्भ

Navigation

Navigation

Wiki tools

Wiki tools

Anonymous

Search

प्लांटेड क्लिक: Difference between revisions

Latest revision as of 15:46, 12 September 2023

परिभाषा

ऊपरी और निचली सीमाएं

एल्गोरिदम

बड़े क्लिक

अर्धबहुपद समय

कठोरता धारणा के रूप में

संदर्भ

Navigation

Wiki tools

Page tools

Other projects

Categories