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.
- 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?
- 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 Архивирано на сајту Wayback Machine (4. март 2016)
- The Open Problems Project
- The RTA list of open problems
