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

{{Short description|Complexity class of problems}}
{{Use American English|date=January 2019}} अभिकलन समस्याएं जो [[जटिलता वर्ग]] एन[[पी (जटिलता)|पी जटिलता]] में हैं लेकिन ये न तो कक्षा पी जटिलता में हैं और न ही एनपी-पूर्ण को एनपी-इंटरमीडिएट कहा जाता है ऐसी समस्याओं के वर्ग को एनपीआई कहा जाता है 1975 में रिचर्ड ई. लैडनर द्वारा दिखाया गया कि लेडनर का प्रमेय <ref>{{cite journal
| first=Richard
| last=Ladner
| title=On the Structure of Polynomial Time Reducibility
| journal=Journal of the ACM
| volume=22
| issue=1
| year=1975
| pages=155–171
| doi=10.1145/321864.321877| s2cid=14352974
}}</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> कुछ समस्याएं जो एनपी-मध्यवर्ती होने के लिए अच्छे उम्मीदवार मानी जाती हैं वे [[ग्राफ समरूपता समस्या]] और [[पूर्णांक गुणनखंडन]] और [[असतत लघुगणक]] की [[निर्णय समस्या]] है। 

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

=== बीजगणित और संख्या सिद्धांत ===
* द्विघात पूर्णांकों का एक निर्णय संस्करण इनपुट के लिए <math>n</math> और <math>k</math> करता है <math>n</math> अंतराल में एक कारक है। <math>[2,k]</math>
* [[असतत लॉग समस्या|असतत प्रारंभ समस्या]] का निर्णय संस्करण और क्रिप्टोग्राफ़िक से संबंधित अन्य तत्व। 
* रैखिक विभाज्यता दिए गए पूर्णांक <math>x</math> और <math>y</math> है <math>y</math> एक विभाजक प्रारूप के अनुरूप है। 


=== बूलियन तर्क ===
* आईएमएसएटी एक लय सीएनएफ को परस्पर काटने करने के लिए बूलियन संतुष्टि की समस्या संयोजक सामान्य रूप से प्रत्येक खंड में केवल सकारात्मक या नकारात्मक शब्द होते हैं और प्रत्येक सकारात्मक खंड में  नकारात्मक खंड के साथ एक चर होता है।<ref>{{cite conference
 | last1 = Eiter | first1 = Thomas
 | last2 = Gottlob | first2 = Georg
 | editor1-last = Flesca | editor1-first = Sergio
 | editor2-last = Greco | editor2-first = Sergio
 | editor3-last = Leone | editor3-first = Nicola
 | editor4-last = Ianni | editor4-first = Giovambattista
 | contribution = Hypergraph transversal computation and related problems in logic and AI
 | doi = 10.1007/3-540-45757-7_53
 | pages = 549–564
 | publisher = Springer
 | series = Lecture Notes in Computer Science
 | title = Logics in Artificial Intelligence, European Conference, JELIA 2002, Cosenza, Italy, September, 23-26, Proceedings
 | volume = 2424
 | year = 2002}}</ref>
* [[बूलियन कार्यों के लिए सर्किट न्यूनीकरण|बूलियन कार्यों के लिए परिपथ न्यूनीकरण]] एक बूलियन कार्यक्रम और धनात्मक पूर्णांक की सत्य तालिका दी गई है <math>s</math> अधिकतम आकार का एक परिपथ एकत्र है <math>s</math> इस समारोह के लिए महत्वपूर्ण है।<ref>{{cite conference
  | first1 =Valentine
  | last1 =Kabanets
  | first2 =Jin-Yi
  | last2 =Cai
  | contribution = Circuit minimization problem
  | title = Proc. 32nd Symposium on Theory of Computing
  | id = {{ECCC|1999|99|045}}
  | year =2000
  | pages =73–79
  | place = Portland, Oregon, USA
  | doi = 10.1145/335305.335314| title-link =Symposium on Theory of Computing
 | s2cid =785205
 | doi-access =free
  }}</ref>
* एकलय स्व-द्वंद्व बूलियन कार्यक्रम के लिए एक सीएनएफ सूत्र दिया गया है क्या कार्यक्रम अपरिवर्तनीय एक परिवर्तन के तहत है जो इसके सभी चरों को अस्वीकार करता है और फिर आउटपुट मान को अस्वीकार करता है <ref>{{cite journal
 | last1 = Eiter | first1 = Thomas
 | last2 = Makino | first2 = Kazuhisa
 | last3 = Gottlob | first3 = Georg
 | doi = 10.1016/j.dam.2007.04.017 | doi-access=free
 | issue = 11
 | journal = [[Discrete Applied Mathematics]]
 | mr = 2437000
 | pages = 2035–2049
 | title = Computational aspects of monotone dualization: a brief survey
 | volume = 156
 | year = 2008| s2cid = 10096898
 }}</ref>


=== अभिकलन ज्यामिति और अभिकलन टोपोलॉजी ===
* इसमें यह निर्धारित करना होता है कि क्या घूर्णन की दूरी <ref>{{cite journal
 | last1 = Sleator | first1 = Daniel D.
 | last2 = Tarjan | first2 = Robert E.
 | last3 = Thurston | first3 = William P.
 | doi = 10.2307/1990951 | doi-access=free
 | issue = 3
 | journal = Journal of the American Mathematical Society
 | mr = 928904
 | pages = 647–681
 | title = Rotation distance, triangulations, and hyperbolic geometry
 | volume = 1
 | year = 1988| jstor = 1990951
 }}</ref> दो बाइनरी पेड़ों के बीच या एक ही उत्तल बहुभुज के दो त्रिकोणों के बीच की विकल्प दूरी दी गई सीमा से नीचे है। 
* उनकी दूरी बहु समूहों से लाइन पर पुनर्निर्माण बिंदुओं की घुमावदार समस्या। <ref>{{cite conference
 | last1 = Skiena | first1 = Steven
 | last2 = Smith | first2 = Warren D.
 | last3 = Lemke | first3 = Paul
 | editor-last = Seidel | editor-first = Raimund
 | contribution = Reconstructing Sets from Interpoint Distances (Extended Abstract)
 | doi = 10.1145/98524.98598
 | pages = 332–339
 | publisher = ACM
 | title = Proceedings of the Sixth Annual Symposium on Computational Geometry, Berkeley, CA, USA, June 6-8, 1990
 | year = 1990}}</ref>
* वस्तु की लंबाई की निरंतर संख्या के साथ सही भन्डार समस्या। <ref>{{cite journal
 | last1 = Jansen | first1 = Klaus
 | last2 = Solis-Oba | first2 = Roberto
 | doi = 10.1287/moor.1110.0515
 | issue = 4
 | journal = Mathematics of Operations Research
 | mr = 2855867
 | pages = 743–753
 | title = A polynomial time OPT + 1 algorithm for the cutting stock problem with a constant number of object lengths
 | volume = 36
 | year = 2011}}</ref>
* गाँठ तुच्छता। <ref>{{cite journal
 | last = Lackenby | first = Marc
 | arxiv = 1604.00290
 | doi = 10.1016/j.aim.2021.107796 | doi-access=free
 | journal = [[Advances in Mathematics]]
 | mr = 4274879
 | page = Paper No. 107796
 | title = The efficient certification of knottedness and Thurston norm
 | volume = 387
 | year = 2021| s2cid = 119307517
 }}</ref>
* उत्तल उदार पर तीन भूगर्भ विज्ञान के प्रमेय का पता लगाना। <ref>{{cite book
 | last1 = Demaine | first1 = Erik D. | author1-link = Erik Demaine
 | last2 = O'Rourke | first2 = Joseph | author2-link = Joseph O'Rourke (professor)
 | contribution = 24 Geodesics: Lyusternik–Schnirelmann
 | doi = 10.1017/CBO9780511735172
 | isbn = 978-0-521-71522-5
 | location = Cambridge
 | mr = 2354878
 | pages = 372–375
 | publisher = Cambridge University Press
 | title = Geometric folding algorithms: Linkages, origami, polyhedra
 | title-link=Geometric Folding Algorithms
 | year = 2007}}.</ref>


=== खेल सिद्धांत ===
* [[ समता खेल ]]में विजेता का निर्धारण करना जिसमें ग्राफ़ कार्यक्षेत्र को बराबर किया जाता है कि कौन सा खिलाड़ी अगला चरण चुनता है और विजेता उच्चतम-प्राथमिकता वाले शीर्ष की समानता से निर्धारित होता है। <ref>{{cite journal
 | last = Jurdziński | first = Marcin
 | doi = 10.1016/S0020-0190(98)00150-1
 | issue = 3
 | journal = Information Processing Letters
 | mr = 1657581
 | pages = 119–124
 | title = Deciding the winner in parity games is in UP <math>\cap</math> co-UP
 | volume = 68
 | year = 1998}}</ref>
* स्टोचैस्टिक ग्राफ़ खेल के लिए विजेता का निर्धारण करना जिसमें ग्राफ़ कार्यक्षेत्र को बराबर किया जाता है जिसके द्वारा खिलाड़ी अगला चरण चुनता है या क्या इसे यादृच्छिक रूप से चुना जाता है और विजेता निर्धारित सिंक कार्यक्षेत्र तक पहुंचकर निर्धारित किया जाता है।<ref>{{cite journal
 | last = Condon | first = Anne
 | doi = 10.1016/0890-5401(92)90048-K
 | issue = 2
 | journal = Information and Computation
 | mr = 1147987
 | pages = 203–224
 | title = The complexity of stochastic games
 | volume = 96
 | year = 1992| doi-access = free
 }}</ref>


=== ग्राफ प्रारूप ===
* ग्राफ समरूपता समस्या। <ref>{{cite book
 | last1 = Grohe | first1 = Martin
 | last2 = Neuen | first2 = Daniel
 | arxiv = 2011.01366
 | contribution = Recent advances on the graph isomorphism problem
 | date = June 2021
 | doi = 10.1017/9781009036214.006
 | pages = 187–234
 | publisher = Cambridge University Press
 | title = Surveys in Combinatorics 2021| s2cid = 226237505
 }}</ref>
* प्लानर [[ग्राफ विभाजन|ग्राफ विभाजन।]]<ref>{{cite conference
 | last = Karpinski | first = Marek
 | editor1-last = Diks | editor1-first = Krzysztof
 | editor2-last = Rytter | editor2-first = Wojciech
 | contribution = Approximability of the minimum bisection problem: an algorithmic challenge
 | doi = 10.1007/3-540-45687-2_4
 | pages = 59–67
 | publisher = Springer
 | series = Lecture Notes in Computer Science
 | title = Mathematical Foundations of Computer Science 2002, 27th International Symposium, MFCS 2002, Warsaw, Poland, August 26-30, 2002, Proceedings
 | volume = 2420
 | year = 2002}}</ref>
* यह तय करना कि क्या कोई ग्राफ़ [[सुंदर लेबलिंग]] स्वीकार करता है। <ref>{{cite journal
 | last = Gallian | first = Joseph A.
 | date = December 17, 2021
 | journal = Electronic Journal of Combinatorics
 | mr = 1668059
 | page = Dynamic Survey 6
 | title = A dynamic survey of graph labeling
 | url = https://www.combinatorics.org/Surveys/index.html
 | volume = 5}}</ref>
* [[पत्ती शक्ति]]यों को पहचानना और {{mvar|k}}-पत्ती शक्तियाँ। <ref>{{cite journal
 | last1 = Nishimura | first1 = N.
 | last2 = Ragde | first2 = P.
 | last3 = Thilikos | first3 = D.M.
 | journal = [[Journal of Algorithms]]
 | pages = 69–108
 | title = On graph powers for leaf-labeled trees
 | volume = 42
 | year = 2002 | doi=10.1006/jagm.2001.1195}}.</ref>
* बंधे हुए [[गुट-चौड़ाई]] नामांकन को पहचानना। <ref>{{cite journal
 | last1 = Fellows | first1 = Michael R. | author1-link = Michael Fellows
 | last2 = Rosamond | first2 = Frances A. | author2-link = Frances A. Rosamond
 | last3 = Rotics | first3 = Udi
 | last4 = Szeider | first4 = Stefan | author4-link = Stefan Szeider
 | doi = 10.1137/070687256
 | issue = 2
 | journal = [[SIAM Journal on Discrete Mathematics]]
 | mr = 2519936
 | pages = 909–939
 | title = Clique-width is NP-complete
 | volume = 23
 | year = 2009}}.</ref>
* निश्चित किनारों के साथ [[एक साथ एम्बेडिंग]] के अस्तित्व का परीक्षण करना। <ref>{{cite conference
 | last1 = Gassner | first1 = Elisabeth
 | last2 = Jünger | first2 = Michael
 | last3 = Percan | first3 = Merijam
 | last4 = Schaefer | first4 = Marcus
 | last5 = Schulz | first5 = Michael
 | contribution = Simultaneous graph embeddings with fixed edges
 | doi = 10.1007/11917496_29
 | mr = 2290741
 | pages = 325–335
 | publisher = Springer | location = Berlin
 | series = Lecture Notes in Computer Science
 | title = Graph-Theoretic Concepts in Computer Science: 32nd International Workshop, WG 2006, Bergen, Norway, June 22-24, 2006, Revised Papers
 | volume = 4271
 | year = 2006| url = http://e-archive.informatik.uni-koeln.de/507/2/zaik2006-507.pdf
 }}.</ref>


=== विविध ===
* परीक्षण करना कि समूह के किसी दिए गए परिवार का वैपनिक-चेर्वोनेंकिस आयाम किसी दिए गए सीमा से नीचे है या नहीं।<ref>{{cite journal
 | last1 = Papadimitriou | first1 = Christos H. | author1-link = Christos Papadimitriou
 | last2 = Yannakakis | first2 = Mihalis | author2-link = Mihalis Yannakakis
 | doi = 10.1006/jcss.1996.0058
 | issue = 2, part 1
 | journal = Journal of Computer and System Sciences
 | mr = 1418886
 | pages = 161–170
 | title = On limited nondeterminism and the complexity of the V-C dimension
 | volume = 53
 | year = 1996| doi-access = free
 }}</ref>


==संदर्भ==
{{Reflist|30em}}


== बाहरी संबंध ==
* {{ComplexityZoo|Class NPI|N#npi}}
* [https://web.archive.org/web/20110727222854/http://users.comlab.ox.ac.uk/luke.ong/teaching/complexity/section5.ps Basic structure, Turing reducibility and NP-hardness]
* {{Cite web
|author=Lance Fortnow
|url=http://oldblog.computationalcomplexity.org/archive/2003_03_23_archive.html#200039297
|title=Foundations of Complexity, Lesson 16: Ladner's Theorem
|accessdate=1 November 2013
|date=24 March 2003}}

{{DEFAULTSORT:Np-Intermediate}}

[[Category:All Wikipedia articles written in American English|Np-Intermediate]]
[[Category:Created On 18/05/2023|Np-Intermediate]]
[[Category:Lua-based templates|Np-Intermediate]]
[[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]]