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

From Vigyanwiki
No edit summary
 
(5 intermediate revisions by 3 users not shown)
Line 17: Line 17:


=== बीजगणित और संख्या सिद्धांत ===
=== बीजगणित और संख्या सिद्धांत ===
* फैक्टरिंग पूर्णांकों का एक निर्णय संस्करण: इनपुट के लिए <math>n</math> और <math>k</math>, करता है <math>n</math> अंतराल में एक कारक है <math>[2,k]</math>?
* द्विघात पूर्णांकों का एक निर्णय संस्करण इनपुट के लिए <math>n</math> और <math>k</math> करता है <math>n</math> अंतराल में एक कारक है। <math>[2,k]</math>
* [[असतत लॉग समस्या]] का निर्णय संस्करण और क्रिप्टोग्राफ़िक मान्यताओं से संबंधित अन्य
* [[असतत लॉग समस्या|असतत प्रारंभ समस्या]] का निर्णय संस्करण और क्रिप्टोग्राफ़िक से संबंधित अन्य तत्व।
* रैखिक विभाज्यता: दिए गए पूर्णांक <math>x</math> और <math>y</math>, करता है <math>y</math> एक विभाजक 1 मॉड्यूलो के अनुरूप है <math>x</math>?<ref>{{cite conference
* रैखिक विभाज्यता दिए गए पूर्णांक <math>x</math> और <math>y</math> है <math>y</math> एक विभाजक प्रारूप के अनुरूप है।
| last1 = Adleman | first1 = Leonard
| last2 = Manders | first2 = Kenneth
| contribution = Reducibility, randomness, and intractibility
| doi = 10.1145/800105.803405
| title = Proceedings of the 9th ACM Symp. on Theory of Computing (STOC '77)
| year = 1977}}</ref><ref>{{cite book|title=अभिकलनात्मक जटिलता|first=Christos H.|last=Papadimitriou|publisher=Addison-Wesley|year=1994|isbn= 9780201530827|page=236}}</ref>




=== बूलियन तर्क ===
=== बूलियन तर्क ===
* IMSAT, मोनोटोन CNF को इंटरसेक्ट करने के लिए बूलियन संतुष्टि की समस्या: संयोजक सामान्य रूप, प्रत्येक खंड में केवल सकारात्मक या केवल नकारात्मक शब्द होते हैं, और प्रत्येक सकारात्मक खंड में प्रत्येक नकारात्मक खंड के साथ एक चर होता है।<ref>{{cite conference
* आईएमएसएटी एक लय सीएनएफ को परस्पर काटने करने के लिए बूलियन संतुष्टि की समस्या संयोजक सामान्य रूप से प्रत्येक खंड में केवल सकारात्मक या नकारात्मक शब्द होते हैं और प्रत्येक सकारात्मक खंड में नकारात्मक खंड के साथ एक चर होता है।<ref>{{cite conference
  | last1 = Eiter | first1 = Thomas
  | last1 = Eiter | first1 = Thomas
  | last2 = Gottlob | first2 = Georg
  | last2 = Gottlob | first2 = Georg
Line 44: Line 38:
  | volume = 2424
  | volume = 2424
  | year = 2002}}</ref>
  | year = 2002}}</ref>
* [[बूलियन कार्यों के लिए सर्किट न्यूनीकरण]]: एक बूलियन फ़ंक्शन और धनात्मक पूर्णांक की सत्य तालिका दी गई है <math>s</math>, क्या अधिकतम आकार का एक सर्किट मौजूद है <math>s</math> इस समारोह के लिए?<ref>{{cite conference
* [[बूलियन कार्यों के लिए सर्किट न्यूनीकरण|बूलियन कार्यों के लिए परिपथ न्यूनीकरण]] एक बूलियन कार्यक्रम और धनात्मक पूर्णांक की सत्य तालिका दी गई है <math>s</math> अधिकतम आकार का एक परिपथ एकत्र है <math>s</math> इस समारोह के लिए महत्वपूर्ण है।<ref>{{cite conference
   | first1 =Valentine
   | first1 =Valentine
   | last1 =Kabanets
   | last1 =Kabanets
Line 59: Line 53:
  | doi-access =free
  | doi-access =free
   }}</ref>
   }}</ref>
* मोनोटोन स्व-द्वंद्व: बूलियन फ़ंक्शन के लिए एक सीएनएफ फॉर्मूला दिया गया है, क्या फ़ंक्शन इनवेरिएंट एक परिवर्तन के तहत है जो इसके सभी चरों को अस्वीकार करता है और फिर आउटपुट मान को अस्वीकार करता है?<ref>{{cite journal
* एकलय स्व-द्वंद्व बूलियन कार्यक्रम के लिए एक सीएनएफ सूत्र दिया गया है क्या कार्यक्रम अपरिवर्तनीय एक परिवर्तन के तहत है जो इसके सभी चरों को अस्वीकार करता है और फिर आउटपुट मान को अस्वीकार करता है <ref>{{cite journal
  | last1 = Eiter | first1 = Thomas
  | last1 = Eiter | first1 = Thomas
  | last2 = Makino | first2 = Kazuhisa
  | last2 = Makino | first2 = Kazuhisa
Line 74: Line 68:




=== कम्प्यूटेशनल ज्यामिति और कम्प्यूटेशनल टोपोलॉजी ===
=== अभिकलन ज्यामिति और अभिकलन टोपोलॉजी ===
* यह निर्धारित करना कि क्या रोटेशन की दूरी है<ref>{{cite journal
* इसमें यह निर्धारित करना होता है कि क्या घूर्णन की दूरी <ref>{{cite journal
  | last1 = Sleator | first1 = Daniel D.
  | last1 = Sleator | first1 = Daniel D.
  | last2 = Tarjan | first2 = Robert E.
  | last2 = Tarjan | first2 = Robert E.
Line 87: Line 81:
  | volume = 1
  | volume = 1
  | year = 1988| jstor = 1990951
  | year = 1988| jstor = 1990951
  }}</ref> दो बाइनरी पेड़ों के बीच या एक ही उत्तल बहुभुज के दो त्रिकोणों के बीच की फ्लिप दूरी दी गई सीमा से नीचे है
  }}</ref> दो बाइनरी पेड़ों के बीच या एक ही उत्तल बहुभुज के दो त्रिकोणों के बीच की विकल्प दूरी दी गई सीमा से नीचे है।
* उनकी दूरी मल्टीसेट से लाइन पर पुनर्निर्माण बिंदुओं की टर्नपाइक समस्या<ref>{{cite conference
* उनकी दूरी बहु समूहों से लाइन पर पुनर्निर्माण बिंदुओं की घुमावदार समस्या। <ref>{{cite conference
  | last1 = Skiena | first1 = Steven
  | last1 = Skiena | first1 = Steven
  | last2 = Smith | first2 = Warren D.
  | last2 = Smith | first2 = Warren D.
Line 99: Line 93:
  | title = Proceedings of the Sixth Annual Symposium on Computational Geometry, Berkeley, CA, USA, June 6-8, 1990
  | title = Proceedings of the Sixth Annual Symposium on Computational Geometry, Berkeley, CA, USA, June 6-8, 1990
  | year = 1990}}</ref>
  | year = 1990}}</ref>
* वस्तु की लंबाई की निरंतर संख्या के साथ कटिंग स्टॉक समस्या<ref>{{cite journal
* वस्तु की लंबाई की निरंतर संख्या के साथ सही भन्डार समस्या। <ref>{{cite journal
  | last1 = Jansen | first1 = Klaus
  | last1 = Jansen | first1 = Klaus
  | last2 = Solis-Oba | first2 = Roberto
  | last2 = Solis-Oba | first2 = Roberto
Line 110: Line 104:
  | volume = 36
  | volume = 36
  | year = 2011}}</ref>
  | year = 2011}}</ref>
* गाँठ तुच्छता<ref>{{cite journal
* गाँठ तुच्छता। <ref>{{cite journal
  | last = Lackenby | first = Marc
  | last = Lackenby | first = Marc
  | arxiv = 1604.00290
  | arxiv = 1604.00290
Line 121: Line 115:
  | year = 2021| s2cid = 119307517
  | year = 2021| s2cid = 119307517
  }}</ref>
  }}</ref>
* उत्तल पॉलीहेड्रॉन पर तीन भूगर्भ विज्ञान के प्रमेय का पता लगाना<ref>{{cite book
* उत्तल उदार पर तीन भूगर्भ विज्ञान के प्रमेय का पता लगाना। <ref>{{cite book
  | last1 = Demaine | first1 = Erik D. | author1-link = Erik Demaine
  | last1 = Demaine | first1 = Erik D. | author1-link = Erik Demaine
  | last2 = O'Rourke | first2 = Joseph | author2-link = Joseph O'Rourke (professor)
  | last2 = O'Rourke | first2 = Joseph | author2-link = Joseph O'Rourke (professor)
Line 262: Line 256:
|date=24 March 2003}}
|date=24 March 2003}}


{{DEFAULTSORT:Np-Intermediate}}[[Category: जटिलता वर्ग]]
{{DEFAULTSORT:Np-Intermediate}}


 
[[Category:All Wikipedia articles written in American English|Np-Intermediate]]
 
[[Category:Created On 18/05/2023|Np-Intermediate]]
[[Category: Machine Translated Page]]
[[Category:Lua-based templates|Np-Intermediate]]
[[Category:Created On 18/05/2023]]
[[Category:Machine Translated Page|Np-Intermediate]]
[[Category:Pages with script errors|Np-Intermediate]]
[[Category:Templates Vigyan Ready|Np-Intermediate]]
[[Category:Templates that add a tracking category|Np-Intermediate]]
[[Category:Templates that generate short descriptions|Np-Intermediate]]
[[Category:Templates using TemplateData|Np-Intermediate]]
[[Category:Use American English from January 2019|Np-Intermediate]]
[[Category:जटिलता वर्ग|Np-Intermediate]]

Latest revision as of 10:52, 29 May 2023

अभिकलन समस्याएं जो जटिलता वर्ग एनपी जटिलता में हैं लेकिन ये न तो कक्षा पी जटिलता में हैं और न ही एनपी-पूर्ण को एनपी-इंटरमीडिएट कहा जाता है ऐसी समस्याओं के वर्ग को एनपीआई कहा जाता है 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’