एनपी-मध्यवर्ती: Difference between revisions

From Vigyanwiki
No edit summary
Line 137: Line 137:


=== खेल सिद्धांत ===
=== खेल सिद्धांत ===
* [[ समता खेल ]] में विजेता का निर्धारण करना, जिसमें ग्राफ़ वर्टिकल को लेबल किया जाता है कि कौन सा खिलाड़ी अगला चरण चुनता है, और विजेता उच्चतम-प्राथमिकता वाले शीर्ष की समानता से निर्धारित होता है<ref>{{cite journal
* [[ समता खेल ]]में विजेता का निर्धारण करना जिसमें ग्राफ़ कार्यक्षेत्र को बराबर किया जाता है कि कौन सा खिलाड़ी अगला चरण चुनता है और विजेता उच्चतम-प्राथमिकता वाले शीर्ष की समानता से निर्धारित होता है। <ref>{{cite journal
  | last = Jurdziński | first = Marcin
  | last = Jurdziński | first = Marcin
  | doi = 10.1016/S0020-0190(98)00150-1
  | doi = 10.1016/S0020-0190(98)00150-1
Line 147: Line 147:
  | volume = 68
  | volume = 68
  | year = 1998}}</ref>
  | year = 1998}}</ref>
* स्टोचैस्टिक ग्राफ़ गेम के लिए विजेता का निर्धारण करना, जिसमें ग्राफ़ वर्टिकल को लेबल किया जाता है, जिसके द्वारा खिलाड़ी अगला चरण चुनता है, या क्या इसे यादृच्छिक रूप से चुना जाता है, और विजेता निर्धारित सिंक वर्टेक्स तक पहुंचकर निर्धारित किया जाता है।<ref>{{cite journal
* स्टोचैस्टिक ग्राफ़ खेल के लिए विजेता का निर्धारण करना जिसमें ग्राफ़ कार्यक्षेत्र को बराबर किया जाता है जिसके द्वारा खिलाड़ी अगला चरण चुनता है या क्या इसे यादृच्छिक रूप से चुना जाता है और विजेता निर्धारित सिंक कार्यक्षेत्र तक पहुंचकर निर्धारित किया जाता है।<ref>{{cite journal
  | last = Condon | first = Anne
  | last = Condon | first = Anne
  | doi = 10.1016/0890-5401(92)90048-K
  | doi = 10.1016/0890-5401(92)90048-K
Line 160: Line 160:




=== ग्राफ एल्गोरिदम ===
=== ग्राफ प्रारूप ===
* ग्राफ समरूपता समस्या<ref>{{cite book
* ग्राफ समरूपता समस्या। <ref>{{cite book
  | last1 = Grohe | first1 = Martin
  | last1 = Grohe | first1 = Martin
  | last2 = Neuen | first2 = Daniel
  | last2 = Neuen | first2 = Daniel
Line 172: Line 172:
  | title = Surveys in Combinatorics 2021| s2cid = 226237505
  | title = Surveys in Combinatorics 2021| s2cid = 226237505
  }}</ref>
  }}</ref>
* प्लानर [[ग्राफ विभाजन]]<ref>{{cite conference
* प्लानर [[ग्राफ विभाजन|ग्राफ विभाजन।]]<ref>{{cite conference
  | last = Karpinski | first = Marek
  | last = Karpinski | first = Marek
  | editor1-last = Diks | editor1-first = Krzysztof
  | editor1-last = Diks | editor1-first = Krzysztof
Line 184: Line 184:
  | volume = 2420
  | volume = 2420
  | year = 2002}}</ref>
  | year = 2002}}</ref>
* यह तय करना कि क्या कोई ग्राफ़ [[सुंदर लेबलिंग]] स्वीकार करता है<ref>{{cite journal
* यह तय करना कि क्या कोई ग्राफ़ [[सुंदर लेबलिंग]] स्वीकार करता है। <ref>{{cite journal
  | last = Gallian | first = Joseph A.
  | last = Gallian | first = Joseph A.
  | date = December 17, 2021
  | date = December 17, 2021
Line 193: Line 193:
  | url = https://www.combinatorics.org/Surveys/index.html
  | url = https://www.combinatorics.org/Surveys/index.html
  | volume = 5}}</ref>
  | volume = 5}}</ref>
* [[पत्ती शक्ति]]यों को पहचानना और {{mvar|k}}-पत्ती शक्तियाँ<ref>{{cite journal
* [[पत्ती शक्ति]]यों को पहचानना और {{mvar|k}}-पत्ती शक्तियाँ। <ref>{{cite journal
  | last1 = Nishimura | first1 = N.
  | last1 = Nishimura | first1 = N.
  | last2 = Ragde | first2 = P.
  | last2 = Ragde | first2 = P.
Line 202: Line 202:
  | volume = 42
  | volume = 42
  | year = 2002 | doi=10.1006/jagm.2001.1195}}.</ref>
  | year = 2002 | doi=10.1006/jagm.2001.1195}}.</ref>
* बंधे हुए [[गुट-चौड़ाई]] के रेखांकन को पहचानना<ref>{{cite journal
* बंधे हुए [[गुट-चौड़ाई]] नामांकन को पहचानना। <ref>{{cite journal
  | last1 = Fellows | first1 = Michael R. | author1-link = Michael Fellows
  | last1 = Fellows | first1 = Michael R. | author1-link = Michael Fellows
  | last2 = Rosamond | first2 = Frances A. | author2-link = Frances A. Rosamond
  | last2 = Rosamond | first2 = Frances A. | author2-link = Frances A. Rosamond
Line 215: Line 215:
  | volume = 23
  | volume = 23
  | year = 2009}}.</ref>
  | year = 2009}}.</ref>
* निश्चित किनारों के साथ [[एक साथ एम्बेडिंग]] के अस्तित्व का परीक्षण करना<ref>{{cite conference
* निश्चित किनारों के साथ [[एक साथ एम्बेडिंग]] के अस्तित्व का परीक्षण करना। <ref>{{cite conference
  | last1 = Gassner | first1 = Elisabeth
  | last1 = Gassner | first1 = Elisabeth
  | last2 = Jünger | first2 = Michael
  | last2 = Jünger | first2 = Michael
Line 234: Line 234:


=== विविध ===
=== विविध ===
* परीक्षण करना कि सेट के किसी दिए गए परिवार का वैपनिक-चेर्वोनेंकिस आयाम किसी दिए गए सीमा से नीचे है या नहीं<ref>{{cite journal
* परीक्षण करना कि समूह के किसी दिए गए परिवार का वैपनिक-चेर्वोनेंकिस आयाम किसी दिए गए सीमा से नीचे है या नहीं।<ref>{{cite journal
  | last1 = Papadimitriou | first1 = Christos H. | author1-link = Christos Papadimitriou
  | last1 = Papadimitriou | first1 = Christos H. | author1-link = Christos Papadimitriou
  | last2 = Yannakakis | first2 = Mihalis | author2-link = Mihalis Yannakakis
  | last2 = Yannakakis | first2 = Mihalis | author2-link = Mihalis Yannakakis

Revision as of 16:30, 22 May 2023

अभिकलन समस्याएं जो जटिलता वर्ग एनपी जटिलता में हैं लेकिन ये न तो कक्षा पी जटिलता में हैं और न ही एनपी-पूर्ण को एनपी-इंटरमीडिएट कहा जाता है ऐसी समस्याओं के वर्ग को एनपीआई कहा जाता है 1975 में रिचर्ड ई. लैडनर द्वारा दिखाया गया कि लेडनर का प्रमेय [1] एक परिणाम है कि अगर पी बनाम एनपी समस्या पी एनपी तो एनपीआई खाली नहीं है एनपी में ऐसी समस्याएं हैं जो न तो पी में हैं और न ही एनपी चूंकि यह भी सच है कि यदि एनपीआई समस्याएं एकत्र हैं तो पी एनपी इस प्रकार है कि पी एनपी और एनपीआई खाली है।

इस धारणा के तहत कि पी एनपी लाडनर स्पष्ट रूप से एनपीआई में एक समस्या का निर्माण करता है यह समस्या कृत्रिम और अरुचिकर है यह एक खुला प्रश्न है कि क्या किसी भी प्राकृतिक समस्या में समान संपत्ति है शेफर की द्विभाजन प्रमेय ऐसी स्थिति प्रदान करता है जिसके तहत एनपीआई में विवश बूलियन संतुष्टि की समस्याएं नहीं हो सकती हैं [2][3] कुछ समस्याएं जो एनपी-मध्यवर्ती होने के लिए अच्छे उम्मीदवार मानी जाती हैं वे ग्राफ समरूपता समस्या और पूर्णांक गुणनखंडन और असतत लघुगणक की निर्णय समस्या है।

उन समस्याओं की सूची जो एनपी-इंटरमीडिएट हो सकती हैं-

बीजगणित और संख्या सिद्धांत

  • फैक्टरिंग पूर्णांकों का एक निर्णय संस्करण: इनपुट के लिए और , करता है अंतराल में एक कारक है ?
  • असतत लॉग समस्या का निर्णय संस्करण और क्रिप्टोग्राफ़िक मान्यताओं से संबंधित अन्य
  • रैखिक विभाज्यता: दिए गए पूर्णांक और , करता है एक विभाजक 1 मॉड्यूलो के अनुरूप है ?[4][5]


बूलियन तर्क

  • IMSAT, मोनोटोन CNF को इंटरसेक्ट करने के लिए बूलियन संतुष्टि की समस्या: संयोजक सामान्य रूप, प्रत्येक खंड में केवल सकारात्मक या केवल नकारात्मक शब्द होते हैं, और प्रत्येक सकारात्मक खंड में प्रत्येक नकारात्मक खंड के साथ एक चर होता है।[6]
  • बूलियन कार्यों के लिए सर्किट न्यूनीकरण: एक बूलियन फ़ंक्शन और धनात्मक पूर्णांक की सत्य तालिका दी गई है , क्या अधिकतम आकार का एक सर्किट मौजूद है इस समारोह के लिए?[7]
  • मोनोटोन स्व-द्वंद्व: बूलियन फ़ंक्शन के लिए एक सीएनएफ फॉर्मूला दिया गया है, क्या फ़ंक्शन इनवेरिएंट एक परिवर्तन के तहत है जो इसके सभी चरों को अस्वीकार करता है और फिर आउटपुट मान को अस्वीकार करता है?[8]


कम्प्यूटेशनल ज्यामिति और कम्प्यूटेशनल टोपोलॉजी

  • यह निर्धारित करना कि क्या रोटेशन की दूरी है[9] दो बाइनरी पेड़ों के बीच या एक ही उत्तल बहुभुज के दो त्रिकोणों के बीच की फ्लिप दूरी दी गई सीमा से नीचे है
  • उनकी दूरी मल्टीसेट से लाइन पर पुनर्निर्माण बिंदुओं की टर्नपाइक समस्या[10]
  • वस्तु की लंबाई की निरंतर संख्या के साथ कटिंग स्टॉक समस्या[11]
  • गाँठ तुच्छता[12]
  • उत्तल पॉलीहेड्रॉन पर तीन भूगर्भ विज्ञान के प्रमेय का पता लगाना[13]


खेल सिद्धांत

  • समता खेल में विजेता का निर्धारण करना जिसमें ग्राफ़ कार्यक्षेत्र को बराबर किया जाता है कि कौन सा खिलाड़ी अगला चरण चुनता है और विजेता उच्चतम-प्राथमिकता वाले शीर्ष की समानता से निर्धारित होता है। [14]
  • स्टोचैस्टिक ग्राफ़ खेल के लिए विजेता का निर्धारण करना जिसमें ग्राफ़ कार्यक्षेत्र को बराबर किया जाता है जिसके द्वारा खिलाड़ी अगला चरण चुनता है या क्या इसे यादृच्छिक रूप से चुना जाता है और विजेता निर्धारित सिंक कार्यक्षेत्र तक पहुंचकर निर्धारित किया जाता है।[15]


ग्राफ प्रारूप


विविध

  • परीक्षण करना कि समूह के किसी दिए गए परिवार का वैपनिक-चेर्वोनेंकिस आयाम किसी दिए गए सीमा से नीचे है या नहीं।[22]


संदर्भ

  1. ↑ Ladner, Richard (1975). "On the Structure of Polynomial Time Reducibility". Journal of the ACM. 22 (1): 155–171. doi:10.1145/321864.321877. S2CID 14352974.
  2. ↑ Grädel, Erich; Kolaitis, Phokion G.; Libkin, Leonid; Marx, Maarten; Spencer, Joel; Vardi, Moshe Y.; Venema, Yde; Weinstein, Scott (2007). परिमित मॉडल सिद्धांत और इसके अनुप्रयोग. Texts in Theoretical Computer Science. An EATCS Series. Berlin: Springer-Verlag. p. 348. ISBN 978-3-540-00428-8. Zbl 1133.03001.
  3. ↑ Schaefer, Thomas J. (1978). "The complexity of satisfiability problems" (PDF). प्रक्रिया। 10वीं एन. एसीएम सिंप। कंप्यूटिंग के सिद्धांत पर. pp. 216–226. MR 0521057.
  4. ↑ Adleman, Leonard; Manders, Kenneth (1977). "Reducibility, randomness, and intractibility". Proceedings of the 9th ACM Symp. on Theory of Computing (STOC '77). doi:10.1145/800105.803405.
  5. ↑ Papadimitriou, Christos H. (1994). अभिकलनात्मक जटिलता. Addison-Wesley. p. 236. ISBN 9780201530827.
  6. ↑ Eiter, Thomas; Gottlob, Georg (2002). "Hypergraph transversal computation and related problems in logic and AI". In Flesca, Sergio; Greco, Sergio; Leone, Nicola; Ianni, Giovambattista (eds.). Logics in Artificial Intelligence, European Conference, JELIA 2002, Cosenza, Italy, September, 23-26, Proceedings. Lecture Notes in Computer Science. Vol. 2424. Springer. pp. 549–564. doi:10.1007/3-540-45757-7_53.
  7. ↑ Kabanets, Valentine; Cai, Jin-Yi (2000). "Circuit minimization problem". Proc. 32nd Symposium on Theory of Computing. Portland, Oregon, USA. pp. 73–79. doi:10.1145/335305.335314. S2CID 785205. ECCC TR99-045.
  8. ↑ Eiter, Thomas; Makino, Kazuhisa; Gottlob, Georg (2008). "Computational aspects of monotone dualization: a brief survey". Discrete Applied Mathematics. 156 (11): 2035–2049. doi:10.1016/j.dam.2007.04.017. MR 2437000. S2CID 10096898.
  9. ↑ Sleator, Daniel D.; Tarjan, Robert E.; Thurston, William P. (1988). "Rotation distance, triangulations, and hyperbolic geometry". Journal of the American Mathematical Society. 1 (3): 647–681. doi:10.2307/1990951. JSTOR 1990951. MR 0928904.
  10. ↑ Skiena, Steven; Smith, Warren D.; Lemke, Paul (1990). "Reconstructing Sets from Interpoint Distances (Extended Abstract)". In Seidel, Raimund (ed.). Proceedings of the Sixth Annual Symposium on Computational Geometry, Berkeley, CA, USA, June 6-8, 1990. ACM. pp. 332–339. doi:10.1145/98524.98598.
  11. ↑ Jansen, Klaus; Solis-Oba, Roberto (2011). "A polynomial time OPT + 1 algorithm for the cutting stock problem with a constant number of object lengths". Mathematics of Operations Research. 36 (4): 743–753. doi:10.1287/moor.1110.0515. MR 2855867.
  12. ↑ Lackenby, Marc (2021). "The efficient certification of knottedness and Thurston norm". Advances in Mathematics. 387: Paper No. 107796. arXiv:1604.00290. doi:10.1016/j.aim.2021.107796. MR 4274879. S2CID 119307517.
  13. ↑ Demaine, Erik D.; O'Rourke, Joseph (2007). "24 Geodesics: Lyusternik–Schnirelmann". Geometric folding algorithms: Linkages, origami, polyhedra. Cambridge: Cambridge University Press. pp. 372–375. doi:10.1017/CBO9780511735172. ISBN 978-0-521-71522-5. MR 2354878..
  14. ↑ Jurdziński, Marcin (1998). "Deciding the winner in parity games is in UP co-UP". Information Processing Letters. 68 (3): 119–124. doi:10.1016/S0020-0190(98)00150-1. MR 1657581.
  15. ↑ Condon, Anne (1992). "The complexity of stochastic games". Information and Computation. 96 (2): 203–224. doi:10.1016/0890-5401(92)90048-K. MR 1147987.
  16. ↑ Grohe, Martin; Neuen, Daniel (June 2021). "Recent advances on the graph isomorphism problem". Surveys in Combinatorics 2021. Cambridge University Press. pp. 187–234. arXiv:2011.01366. doi:10.1017/9781009036214.006. S2CID 226237505.
  17. ↑ Karpinski, Marek (2002). "Approximability of the minimum bisection problem: an algorithmic challenge". In Diks, Krzysztof; Rytter, Wojciech (eds.). Mathematical Foundations of Computer Science 2002, 27th International Symposium, MFCS 2002, Warsaw, Poland, August 26-30, 2002, Proceedings. Lecture Notes in Computer Science. Vol. 2420. Springer. pp. 59–67. doi:10.1007/3-540-45687-2_4.
  18. ↑ Gallian, Joseph A. (December 17, 2021). "A dynamic survey of graph labeling". Electronic Journal of Combinatorics. 5: Dynamic Survey 6. MR 1668059.
  19. ↑ Nishimura, N.; Ragde, P.; Thilikos, D.M. (2002). "On graph powers for leaf-labeled trees". Journal of Algorithms. 42: 69–108. doi:10.1006/jagm.2001.1195..
  20. ↑ Fellows, Michael R.; Rosamond, Frances A.; Rotics, Udi; Szeider, Stefan (2009). "Clique-width is NP-complete". SIAM Journal on Discrete Mathematics. 23 (2): 909–939. doi:10.1137/070687256. MR 2519936..
  21. ↑ Gassner, Elisabeth; Jünger, Michael; Percan, Merijam; Schaefer, Marcus; Schulz, Michael (2006). "Simultaneous graph embeddings with fixed edges". Graph-Theoretic Concepts in Computer Science: 32nd International Workshop, WG 2006, Bergen, Norway, June 22-24, 2006, Revised Papers (PDF). Lecture Notes in Computer Science. Vol. 4271. Berlin: Springer. pp. 325–335. doi:10.1007/11917496_29. MR 2290741..
  22. ↑ Papadimitriou, Christos H.; Yannakakis, Mihalis (1996). "On limited nondeterminism and the complexity of the V-C dimension". Journal of Computer and System Sciences. 53 (2, part 1): 161–170. doi:10.1006/jcss.1996.0058. MR 1418886.


बाहरी संबंध

Retrieved from ‘https://www.vigyanwiki.in/index.php?title=एनपी-मध्यवर्ती&oldid=171814’