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

From Vigyanwiki
(Created page with "{{Short description|Complexity class of problems}} {{Use American English|date=January 2019}} कम्प्यूटेशनल जटिलता सिद्धां...")
 
No edit summary
 
(7 intermediate revisions by 3 users not shown)
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> कुछ समस्याएं जो एनपी-मध्यवर्ती होने के लिए अच्छे उम्मीदवार मानी जाती हैं वे [[ग्राफ समरूपता समस्या]] और [[पूर्णांक गुणनखंडन]] और [[असतत लघुगणक]] की [[निर्णय समस्या]] है।


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


=== बीजगणित और संख्या सिद्धांत ===
=== बीजगणित और संख्या सिद्धांत ===
* फैक्टरिंग पूर्णांकों का एक निर्णय संस्करण: इनपुट के लिए <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 45: 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 60: 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 75: 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 88: 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 100: 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 111: 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 122: 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 138: Line 131:


=== खेल सिद्धांत ===
=== खेल सिद्धांत ===
* [[ समता खेल ]] में विजेता का निर्धारण करना, जिसमें ग्राफ़ वर्टिकल को लेबल किया जाता है कि कौन सा खिलाड़ी अगला चरण चुनता है, और विजेता उच्चतम-प्राथमिकता वाले शीर्ष की समानता से निर्धारित होता है<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 148: Line 141:
  | 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 161: Line 154:




=== ग्राफ एल्गोरिदम ===
=== ग्राफ प्रारूप ===
* ग्राफ समरूपता समस्या<ref>{{cite book
* ग्राफ समरूपता समस्या। <ref>{{cite book
  | last1 = Grohe | first1 = Martin
  | last1 = Grohe | first1 = Martin
  | last2 = Neuen | first2 = Daniel
  | last2 = Neuen | first2 = Daniel
Line 173: Line 166:
  | 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 185: Line 178:
  | 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 194: Line 187:
  | 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 203: Line 196:
  | 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 216: Line 209:
  | 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 235: Line 228:


=== विविध ===
=== विविध ===
* परीक्षण करना कि सेट के किसी दिए गए परिवार का वैपनिक-चेर्वोनेंकिस आयाम किसी दिए गए सीमा से नीचे है या नहीं<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
Line 263: 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’