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 informatice . Problém v počítačové vědě 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í náročnost

Problém P versus NP
Jaký je vztah mezi BQP a NP ?
NC = P problém
NP = co-NP problém
P = problém s BPP
P = problém PSPACE
L = problém NL
PH = problém PSPACE
L = P problém
L = problém RL
Unikátní dohady o hrách
Je hypotéza exponenciálního času pravdivá?
- Je silná hypotéza exponenciálního času (SETH) pravdivá?
Dělat jednosměrné funkce existují?
- Je kryptografie veřejného klíče možná?
Log-rank dohady

Polynomický versus nepolynomiální čas pro specifické algoritmické problémy

Lze celočíselnou faktorizaci provést v polynomiálním čase na klasickém (nekvantovém) počítači?
Lze diskrétní logaritmus vypočítat v polynomiálním čase na klasickém (nekvantovém) počítači?
Lze nejkratší vektor mřížky vypočítat v polynomiálním čase na klasickém nebo kvantovém počítači?
Lze v polynomiálním čase nalézt seskupené rovinné kresby ?
Lze problém izomorfismu grafu vyřešit v polynomiálním čase?
Lze v polynomiálním čase rozeznat listové síly a $k$ -listové síly?
Lze paritní hry řešit v polynomiálním čase?
Lze rotační vzdálenost mezi dvěma binárními stromy vypočítat v polynomiálním čase?
Lze grafy omezené šířky kliky rozpoznat v polynomiálním čase?
Lze na konvexním mnohostěnu v polynomiálním čase najít jednoduchý uzavřený kvazigeodický ?
Lze v polynomiálním čase najít simultánní vkládání s pevnými hranami pro dva dané grafy?

Jiné algoritmické problémy

Dynamický optimalita domněnku : dělat splay strom mít konkurenční poměr ohraničenou?
Existuje $k$ -konkurenční online algoritmus pro problém $k$ -serveru ?
Lze v NC zkonstruovat strom hledání první hloubky ?
Lze rychlou Fourierovu transformaci vypočítat za čas $o (n log n)$ ?
Jaký je nejrychlejší algoritmus pro násobení dvou n -digitálních čísel?
Jaká je nejnižší možná průměrná časová složitost Shellsortu s deterministickou, fixní mezerou?
Lze 3SUM vyřešit v silně subkvadratickém čase, tedy v čase $O (n 2 - ϵ)$ pro nějaké $ϵ> 0$ ?
Lze vzdálenost úprav mezi dvěma řetězci délky $n$ vypočítat v silně subkvadratickém čase? (To je možné pouze tehdy, je -li silná exponenciální časová hypotéza falešná.)
Lze řazení X + Y provést v čase $o (n 2 log n)$ ?
Jaký je nejrychlejší algoritmus pro násobení matic ?
Mohou být všechny páry nejkratších cest vypočítány v silně sub-krychlovém čase, tj. V čase $O (V 3 - ϵ)$ pro nějaké $ϵ> 0$ ?
Může Schwartz-Zippel lemma pro testování polynomu identity být derandomized ?
Má lineární programování připustí silně polynomial -time algoritmus? (Toto je problém č. 9 v seznamu problémů Smale .)
Kolik dotazů je potřeba na krájení dortů bez závisti ?
Jaký je algoritmus pro vyhledávací tabulku, která konzistentně generuje hratelné bludiště ve hře Atari 2600 z roku 1982 Entombed pouze z hodnot pěti pixelů sousedících s dalšími, které mají být generovány?
Jaká je algoritmická složitost minimálního překlenovacího stromu ? Ekvivalentně, jaká je složitost rozhodovacího stromu problému MST? Optimální algoritmus pro výpočet MST je znám , ale spoléhá se na rozhodovací stromy, takže jeho složitost není známa.

Algoritmy pro zpracování přirozeného jazyka

Existuje v angličtině nějaký dokonalý slabikovací algoritmus?
Je nějaká dokonalá vyplývající algoritmus v angličtině?
Existuje v angličtině nějaký perfektní algoritmus blokování frází ?
Jak mohou počítače rozeznat nejednoznačnost zájmena v anglickém jazyce? (Také známý jako Winograd Schema Challenge ).

Teorie programovacího jazyka

Jiné problémy

Reference

externí odkazy

Otevřené problémy kolem exaktních algoritmů od Gerharda J. Woegingera , Discrete Applied Mathematics 156 (2008) 397–405.
Seznam otevřených problémů RTA - otevřené problémy při přepisování .
Seznam otevřených problémů TLCA - otevřené problémy v oblasti lambda kalkulu s typem oblasti .

Languages

In other projects