Nerazjašnjeni problemi u računarskim naukama

Ovaj članak predstavlja spisak nerešenih problema u računarstvu. Problem u računarskim naukama se smatra nerešenim ukoliko ekspert u toj oblasti smatra da je problem nerešiv ili kada se nekoliko stručnjaka u datoj oblasti ne slože o rešenju problema.

Računska kompleksnost

P nasuprot NP problem (često se pise kao "P=NP", sto tehnički nije tačno)
NC=P problem
NP=co-NP problem
P=BPP problem
P = PSPACE problem
L=NL problem
L=P problem
Kakav je odnos između BQP i NP?
Pretpostavka jedinstvenih igara
Da li je hipoteza eksponencijalnog vremena istinita?
Da li postoje jednosmerne funkcije?
Da li je moguća kriptografija sa javnim ključem?

Algoritmi

Koji je najbrži algoritam za množenje dva n-cifrena broja?
Koji je najbrži algoritam za množenje matrica?
Da li faktorizacija celih brojeva može da se uradi u polinomijalnom vremenu na klasičnom računaru?
Da li diskretni algoritam može da se izračuna u polinomijalnom vremenu na klasičnom računaru?
Da li problem izomorfizma grafova može da se reši u polinomijalnom vremenu?
Da li parity igre mogu da se reše u polinomijalnom vremenu?
Da li rastojanje rotacije između dva binarna stabla može da se izračuna u polinomijalnom vremenu?
Da li linearno programiranje priznaje algoritme u polinomijalnom vremenu? Ovo je 9. problem na Smalovoj listi problema.
Koja je donja granica složenosti brzog Furijeovog algoritma transformacija? Može li biti brži od O(NlogN)?
Pretpostavka dinamičke optimalnosti za rašireno drvo?
Problem K-servera
Da li X+Y sortiranje može da se obavi za manje od O(n2logN) vremena?