Seznam nevyřešených problémů v informatice - List of unsolved problems in computer science
Tento článek je seznam pozoruhodných nevyřešených problémů v počítačová věda. Problém v informatice je považován za nevyřešený, pokud není známo žádné řešení, nebo když odborníci v oboru nesouhlasí s navrhovanými řešeními.
Výpočetní složitost
- Problém P versus NP
- Jaký je vztah mezi BQP a NP ?
- NC = P problém
- NP = problém co-NP
- P = problém BPP
- P = problém PSPACE
- L = NL problém
- PH = problém PSPACE
- L = P problém
- L = RL problém
- Unikátní domněnky o hrách
- Je exponenciální časová hypotéza skutečný?
- Je silná exponenciální časová hypotéza (SETH) pravdivá?
- Dělat jednosměrné funkce existovat?
- Je kryptografie veřejného klíče možný?
- Log-rank domněnka
Polynomiální versus nepolynomiální čas pro specifické algoritmické problémy
- Umět celočíselná faktorizace být provedeno v polynomiální čas na klasickém (nekvantovém) počítači?
- Může diskrétní logaritmus být vypočítán v polynomiálním čase?
- Může nejkratší vektor mřížky se počítá v polynomiálním čase na klasickém nebo kvantovém počítači?
- Umět seskupené planární kresby být nalezen v polynomiálním čase?
- Může problém grafového izomorfismu být vyřešen v polynomiálním čase?
- Umět listové síly a k- listové síly budou rozpoznány v polynomiálním čase?
- Umět paritní hry být vyřešen v polynomiálním čase?
- Může rotační vzdálenost mezi dvěma binární stromy být vypočítán v polynomiálním čase?
- Může grafy ohraničené šířka kliky být rozpoznán v polynomiálním čase?[1]
- Může někdo najít a jednoduchá uzavřená kvazigeódika na konvexním mnohostěnu v polynomiálním čase?[2]
- Může a současné vkládání s pevnými hranami pro dva dané grafy lze nalézt v polynomiálním čase?[3]
Další algoritmické problémy
- The domněnka dynamické optimality: mají rozložené stromy omezený konkurenční poměr?
- Existuje k-konkurenční online algoritmus pro k-server problém ?
- Může a hloubkový první vyhledávací strom být postaven v NC ?
- Může rychlá Fourierova transformace být vypočítán v Ó(n log n) čas?
- Co je nejrychlejší algoritmus pro násobení ze dvou n-místná čísla?
- Jaká je nejnižší možná průměrná časová složitost Shellsort s deterministickou posloupností s pevnou mezerou?
- Umět 3SUM být vyřešeny v silně subkvadratickém čase, tj. v čase Ó(n2 − ϵ) pro některé ϵ> 0?
- Může upravit vzdálenost mezi dvěma řetězci délky n být vypočítán v silně subkvadratickém čase? (To je možné pouze v případě, že silný exponenciální časová hypotéza je nepravdivé.)
- Umět Třídění X + Y být provedeno v Ó(n2) čas?
- Co je nejrychlejší algoritmus pro násobení matic ?
- Umět nejkratší cesty všech párů být vypočítán v silně subkubickém čase, tj. v čase Ó(PROTI3 − ϵ) pro některé ϵ> 0?
- Může Schwartz – Zippelovo lemma pro polynomiální testování identity být derandomizováno ?
- Ano lineární programování přiznat a silně polynomický -časový algoritmus? (Toto je problém č. 9 v Smaleův seznam problémů.)
- Kolik dotazů je požadováno řezání dortů bez závisti ?
- Jaký je algoritmus pro vyhledávací tabulka který důsledně generuje hratelné bludiště v roce 1982 Atari 2600 hra Pohřben pouze z hodnot pěti pixelů sousedících s následujícími, které mají být generovány?
Algoritmy zpracování přirozeného jazyka
- Existuje nějaký dokonalý slabikování algoritmus v anglickém jazyce?
- Existuje nějaký dokonalý pramenící algoritmus v anglickém jazyce?
- Existuje nějaký dokonalý Značení POS algoritmus v anglickém jazyce?
- Jak mohou počítače rozeznat nejednoznačnost zájmen v anglickém jazyce? (Také známý jako Winograd Schema Challenge ).
Teorie programovacího jazyka
Další problémy
Reference
- ^ Fellows, Michael R.; Rosamond, Frances A.; Rotics, Udi; Szeider, Stefan (2009), „Šířka kliky je NP úplná“ (PDF), SIAM Journal on Discrete Mathematics, 23 (2): 909–939, doi:10.1137/070687256, PAN 2519936.
- ^ 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.
- ^ Gassner, Elisabeth; Jünger, Michael; Percan, Merijam; Schaefer, Marcus; Schulz, Michael (2006), "Simultánní vkládání grafů s pevnými hranami" (PDF), 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.
externí odkazy
- Otevřené problémy týkající se přesných algoritmů podle Gerhard J. Woeginger „Discrete Applied Mathematics 156 (2008) 397–405.
- Seznam RTA otevřených problémů - otevřené problémy v přepis.
- Seznam otevřených problémů TLCA - otevřené problémy v oblasti zadaný lambda kalkul.