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

From Vigyanwiki
(Created page with "{{Short description|Complexity class of problems}} {{Use American English|date=January 2019}} कम्प्यूटेशनल जटिलता सिद्धां...")
 
No edit summary
Line 1: Line 1:
{{Short description|Complexity class of problems}}
{{Short description|Complexity class of problems}}
{{Use American English|date=January 2019}}
{{Use American English|date=January 2019}} अभिकलन समस्याएं जो [[जटिलता वर्ग]] एन[[पी (जटिलता)|पी जटिलता]] में हैं लेकिन ये न तो कक्षा पी जटिलता में हैं और न ही एनपी-पूर्ण को एनपी-इंटरमीडिएट कहा जाता है ऐसी समस्याओं के वर्ग को एनपीआई कहा जाता है 1975 में रिचर्ड ई. लैडनर द्वारा दिखाया गया कि लेडनर का प्रमेय <ref>{{cite journal
[[कम्प्यूटेशनल जटिलता सिद्धांत]] में, समस्याएं जो [[जटिलता वर्ग]] एन[[पी (जटिलता)]] में हैं, लेकिन न तो कक्षा पी (जटिलता) में हैं और न ही एनपी-पूर्ण को एनपी-इंटरमीडिएट कहा जाता है, और ऐसी समस्याओं के वर्ग को एनपीआई कहा जाता है। 1975 में रिचर्ड ई. लैडनर द्वारा दिखाया गया लेडनर का प्रमेय,<ref>{{cite journal
| first=Richard
| first=Richard
| last=Ladner
| last=Ladner
Line 11: Line 10:
| pages=155–171
| pages=155–171
| doi=10.1145/321864.321877| s2cid=14352974
| doi=10.1145/321864.321877| s2cid=14352974
}}</ref> एक परिणाम है कि, अगर पी बनाम एनपी समस्या | पी ≠ एनपी, तो एनपीआई खाली नहीं है; यानी, एनपी में ऐसी समस्याएं हैं जो न तो पी में हैं और न ही एनपी-पूर्ण। चूंकि यह भी सच है कि यदि एनपीआई समस्याएं मौजूद हैं, तो पी ≠ एनपी, यह इस प्रकार है कि पी = एनपी अगर और केवल एनपीआई खाली है।
}}</ref> एक परिणाम है कि अगर पी बनाम एनपी समस्या पी एनपी तो एनपीआई खाली नहीं है एनपी में ऐसी समस्याएं हैं जो न तो पी में हैं और न ही एनपी चूंकि यह भी सच है कि यदि एनपीआई समस्याएं एकत्र हैं तो पी एनपी इस प्रकार है कि पी एनपी और एनपीआई खाली है।


इस धारणा के तहत कि पी ≠ एनपी, लाडनर स्पष्ट रूप से एनपीआई में एक समस्या का निर्माण करता है, हालांकि यह समस्या कृत्रिम और अन्यथा अरुचिकर है। यह एक खुला प्रश्न है कि क्या किसी भी प्राकृतिक समस्या में समान संपत्ति है: शेफर का द्विभाजन प्रमेय ऐसी स्थिति प्रदान करता है जिसके तहत एनपीआई में विवश बूलियन संतुष्टि की समस्याएं नहीं हो सकती हैं।<ref>{{cite book | last1=Grädel | first1=Erich | last2=Kolaitis | first2=Phokion G. | last3=Libkin | first3=Leonid | first4=Maarten | last4=Marx | last5=Spencer | first5=Joel | author5-link=Joel Spencer | last6=Vardi | first6=Moshe Y. | author6-link=Moshe Y. Vardi | last7=Venema | first7=Yde | last8=Weinstein | first8=Scott | title=परिमित मॉडल सिद्धांत और इसके अनुप्रयोग| zbl=1133.03001 | series=Texts in Theoretical Computer Science. An EATCS Series | location=Berlin | publisher=[[Springer-Verlag]] | isbn=978-3-540-00428-8 | year=2007 | page=348 }}</ref><ref>{{cite book | contribution-url=http://www.ccs.neu.edu/home/lieber/courses/csg260/f06/materials/papers/max-sat/p216-schaefer.pdf | author=Schaefer, Thomas J. | author-link=Thomas Jerome Schaefer | contribution=The complexity of satisfiability problems | title=प्रक्रिया। 10वीं एन. एसीएम सिंप। कंप्यूटिंग के सिद्धांत पर| pages=216&ndash;226 | year=1978 |mr= 521057}}</ref> कुछ समस्याएं जो एनपी-मध्यवर्ती होने के लिए अच्छे उम्मीदवार मानी जाती हैं, वे हैं [[ग्राफ समरूपता समस्या]], और [[पूर्णांक गुणनखंडन]] और [[असतत लघुगणक]] की [[निर्णय समस्या]]।
इस धारणा के तहत कि पी एनपी लाडनर स्पष्ट रूप से एनपीआई में एक समस्या का निर्माण करता है यह समस्या कृत्रिम और अरुचिकर है यह एक खुला प्रश्न है कि क्या किसी भी प्राकृतिक समस्या में समान संपत्ति है शेफर की द्विभाजन प्रमेय ऐसी स्थिति प्रदान करता है जिसके तहत एनपीआई में विवश बूलियन संतुष्टि की समस्याएं नहीं हो सकती हैं <ref>{{cite book | last1=Grädel | first1=Erich | last2=Kolaitis | first2=Phokion G. | last3=Libkin | first3=Leonid | first4=Maarten | last4=Marx | last5=Spencer | first5=Joel | author5-link=Joel Spencer | last6=Vardi | first6=Moshe Y. | author6-link=Moshe Y. Vardi | last7=Venema | first7=Yde | last8=Weinstein | first8=Scott | title=परिमित मॉडल सिद्धांत और इसके अनुप्रयोग| zbl=1133.03001 | series=Texts in Theoretical Computer Science. An EATCS Series | location=Berlin | publisher=[[Springer-Verlag]] | isbn=978-3-540-00428-8 | year=2007 | page=348 }}</ref><ref>{{cite book | contribution-url=http://www.ccs.neu.edu/home/lieber/courses/csg260/f06/materials/papers/max-sat/p216-schaefer.pdf | author=Schaefer, Thomas J. | author-link=Thomas Jerome Schaefer | contribution=The complexity of satisfiability problems | title=प्रक्रिया। 10वीं एन. एसीएम सिंप। कंप्यूटिंग के सिद्धांत पर| pages=216&ndash;226 | year=1978 |mr= 521057}}</ref> कुछ समस्याएं जो एनपी-मध्यवर्ती होने के लिए अच्छे उम्मीदवार मानी जाती हैं वे [[ग्राफ समरूपता समस्या]] और [[पूर्णांक गुणनखंडन]] और [[असतत लघुगणक]] की [[निर्णय समस्या]] है।


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


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

Revision as of 16:21, 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=171813’