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?
Teorija programskih jezika POPLmarka Barendregt - Geuvers-Klop pretpostavka
Drugi problemi Andera-Karp-Rosenberg pretpostavka Problem generalizovane visine zvezde Problem razdvajanja reči
Literatura Major unsolved problems in theoretical computer science Open problems about exact algorithms The Open Problems Project The RTA list of open problems
Категорија:Конјектуре Категорија:Рачунарство