NP-střední - NP-intermediate - Wikipedia
 | Některé z tohoto článku uvedené zdroje nemusí být spolehlivý. (Říjen 2015) (Zjistěte, jak a kdy odstranit tuto zprávu šablony) |
v výpočetní složitost, problémy, které jsou v třída složitosti NP ale nejsou ani ve třídě P ani NP-kompletní jsou nazývány NP-střednía nazývá se třída takových problémů NPI. Ladnerova věta, zobrazeno v roce 1975 autorem Richard E. Ladner,[1] je výsledek tvrdí, že pokud P ≠ NP, pak NPI není prázdný; to znamená, že NP obsahuje problémy, které nejsou ani v P, ani v NP-úplné. Protože je také pravda, že pokud existují problémy NPI, pak P ≠ NP, vyplývá z toho, že P = NP právě tehdy, když je NPI prázdný.
Za předpokladu, že P ≠ NP, Ladner výslovně konstruuje problém v NPI, i když je tento problém umělý a jinak nezajímavý. Je otevřenou otázkou, zda má jakýkoli „přirozený“ problém stejnou vlastnost: Schaeferova věta o dichotomii poskytuje podmínky, za kterých třídy omezených booleovských problémů s uspokojivostí nemohou být v NPI.[2][3] Některé problémy, které jsou považovány za dobré kandidáty na to, aby byly NP-střední, jsou problém grafového izomorfismu, factoring a výpočet diskrétní logaritmus.[4]
Seznam problémů, které by mohly být NP-střední[4]
Algebra a teorie čísel
- Faktorování celých čísel
- Diskrétní problém protokolu a další související s kryptografickými předpoklady
- Problémy s izomorfismem: Problém skupinového izomorfismu, Skupinový automorfismus, Prstencový izomorfismus, Prstencový automorfismus
- Problémy s čísly v krabicích[5]
- Problém lineární dělitelnosti[6]
Logická logika
Výpočetní geometrie a výpočetní topologie
- Výpočet rotační vzdálenost[11] mezi dvěma binární stromy nebo překlopná vzdálenost mezi dvěma triangulacemi stejného konvexního mnohoúhelníku
- Problém s dálnicí[12] rekonstrukce bodů on-line z jejich vzdálené multisety
- The problém řezného materiálu s konstantním počtem délek objektů[13]
- Uzel maličkost[14]
- Rozhodování, zda daný trojúhelníkový 3-potrubí je 3-koule
- Mezerová verze nejbližšího vektoru v mřížkový problém[15]
- Hledání a jednoduchá uzavřená kvazigeódika na konvexním mnohostěnu[16]
Herní teorie
- Určení vítěze v paritní hry[17]
- Určení, kdo má nejvyšší šanci na výhru stochastické hry[17]
- Kontrola agendy pro vyvážené turnaje s jednou eliminací[18]
Algoritmy grafů
- Problém grafového izomorfismu
- Rovinný minimální půlení[19]
- Rozhodování, zda graf připouští a elegantní označení[20]
- Uznávám listové síly a k- listové síly[21]
- Rozpoznávání grafů ohraničených šířka kliky[22]
- Hledání a současné vkládání s pevnými hranami[23]
Smíšený
- Za předpokladu NEXP se nerovná EXP, polstrované verze problémů NEXP-complete
- Problémy v TFNP[24]
- Součet podmnožiny holubí díry[25]
- Nalezení VC rozměr[26]
Reference
- ^ Ladner, Richard (1975). "O struktuře polynomiální časové redukovatelnosti". Deník ACM. 22 (1): 155–171. doi:10.1145/321864.321877. S2CID 14352974.
- ^ Grädel, Erich; Kolaitis, Phokion G .; Libkin, Leonid; Marx, Maarten; Spencer, Joel; Vardi, Moshe Y.; Venema, Yde; Weinstein, Scott (2007). Teorie konečných modelů a její aplikace. Texty v teoretické informatice. Řada EATCS. Berlín: Springer-Verlag. str. 348. ISBN 978-3-540-00428-8. Zbl 1133.03001.
- ^ Schaefer, Thomas J. (1978). „Složitost problémů s uspokojivostí“ (PDF). Proc. 10. Ann. ACM Symp. o teorii výpočtu. 216–226. PAN 0521057.
- ^ A b „Problémy mezi P a NPC“. Teoretická informatická výměna zásobníků. 20. srpna 2011. Citováno 1. listopadu 2013.
- ^ http://blog.computationalcomplexity.org/2010/07/what-is-complexity-of-these-problems.html
- ^ https://cstheory.stackexchange.com/q/4331
- ^ https://cstheory.stackexchange.com/q/1739
- ^ https://cstheory.stackexchange.com/q/1745
- ^ Kabanets, Valentine; Cai, Jin-Yi (2000), „Problém s minimalizací obvodu“, Proc. 32. symposium o teorii práce na počítači, Portland, Oregon, USA, s. 73–79, doi:10.1145/335305.335314, S2CID 785205, ECCC TR99-045
- ^ https://cstheory.stackexchange.com/q/3950
- ^ Rotační vzdálenost, triangulace a hyperbolická geometrie
- ^ Rekonstrukce sad ze vzdáleností mezi body
- ^ https://cstheory.stackexchange.com/q/3827
- ^ https://cstheory.stackexchange.com/q/1106
- ^ https://cstheory.stackexchange.com/q/7806
- ^ Demaine, Erik D.; O'Rourke, Josephe (2007), „24 Geodesics: Lyusternik – Schnirelmann“, Algoritmy geometrického skládání: Vazby, origami, mnohostěny, Cambridge: Cambridge University Press, s. 372–375, doi:10.1017 / CBO9780511735172, ISBN 978-0-521-71522-5, PAN 2354878.
- ^ A b http://kintali.wordpress.com/2010/06/06/np-intersect-conp/
- ^ https://cstheory.stackexchange.com/q/460
- ^ Přibližnost problému minimální půlení: Algoritmická výzva
- ^ https://cstheory.stackexchange.com/q/6384
- ^ 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.
- ^ Fellows, Michael R.; Rosamond, Frances A.; Rotics, Udi; Szeider, Stefan (2009), „Šířka kliky je NP-úplná“, SIAM Journal on Discrete Mathematics, 23 (2): 909–939, doi:10.1137/070687256, PAN 2519936.
- ^ Gassner, Elisabeth; Jünger, Michael; Percan, Merijam; Schaefer, Marcus; Schulz, Michael (2006), „Simultánní vkládání grafů s pevnými hranami“, Graficko-teoretické koncepty v informatice: 32. mezinárodní workshop, WG 2006, Bergen, Norsko, 22. – 24. Června 2006, revidované práce (PDF), Přednášky v informatice, 4271, Berlín: Springer, s. 325–335, doi:10.1007/11917496_29, PAN 2290741.
- ^ Na celkové funkce, věty o existenci a výpočetní složitost
- ^ http://www.openproblemgarden.org/?q=op/theoretical_computer_science/subset_sums_equality
- ^ Papadimitriou, Christos H.; Yannakakis, Mihalis (1996), „O omezeném nedeterminismu a složitosti dimenze V-C“, Journal of Computer and System Sciences, 53 (2, část 1): 161–170, doi:10.1006 / jcss.1996.0058, PAN 1418886
externí odkazy
- Složitost Zoo: Třída NPI
- Základní struktura, Turingova redukovatelnost a NP-tvrdost
- Lance Fortnow (24. března 2003). „Základy složitosti, lekce 16: Ladnerova věta“. Citováno 1. listopadu 2013.