एनपी-मध्यवर्ती

From Vigyanwiki

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

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

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

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

  • द्विघात पूर्णांकों का एक निर्णय संस्करण इनपुट के लिए और करता है अंतराल में एक कारक है।
  • असतत प्रारंभ समस्या का निर्णय संस्करण और क्रिप्टोग्राफ़िक से संबंधित अन्य तत्व।
  • रैखिक विभाज्यता दिए गए पूर्णांक और है एक विभाजक प्रारूप के अनुरूप है।


बूलियन तर्क

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


अभिकलन ज्यामिति और अभिकलन टोपोलॉजी

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


खेल सिद्धांत

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


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


विविध

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


संदर्भ

  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. ↑ 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.
  5. ↑ 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.
  6. ↑ 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.
  7. ↑ 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.
  8. ↑ 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.
  9. ↑ 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.
  10. ↑ 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.
  11. ↑ 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..
  12. ↑ 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.
  13. ↑ 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.
  14. ↑ 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.
  15. ↑ 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.
  16. ↑ Gallian, Joseph A. (December 17, 2021). "A dynamic survey of graph labeling". Electronic Journal of Combinatorics. 5: Dynamic Survey 6. MR 1668059.
  17. ↑ 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..
  18. ↑ 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..
  19. ↑ 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..
  20. ↑ 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=172128’