Неразјашњени проблеми у рачунарским наукама
Овај чланак представља списак нерешених проблема у рачунарству. Проблем у рачунарским наукама се сматра нерешеним уколико експерт у тој области сматра да је проблем нерешив или када се неколико стручњака у датој области не сложе о решењу проблема.
Рачунска комплексност[уреди | уреди извор]
- П насупрот НП проблем (често се писе као "П=НП", сто технички није тачно)
- НЦ=П проблем
- НП=цо-НП проблем
- П=БПП проблем
- П = ПСПАЦЕ проблем
- L=НЛ проблем
- L=П проблем
- Какав је однос између БQП и НП?
- Претпоставка јединствених игара
- Да ли је хипотеза експоненцијалног времена истинита?
- Да ли постоје једносмерне функције?
- Да ли је могућа криптографија са јавним кључем?
Алгоритми[уреди | уреди извор]
- Који је најбржи алгоритам за множење два н-цифрена броја?
- Који је најбржи алгоритам за множење матрица?
- Да ли факторизација целих бројева може да се уради у полиномијалном времену на класичном рачунару?
- Да ли дискретни алгоритам може да се израчуна у полиномијалном времену на класичном рачунару?
- Да ли проблем изоморфизма графова може да се реши у полиномијалном времену?
- Да ли паритy игре могу да се реше у полиномијалном времену?
- Да ли растојање ротације између два бинарна стабла може да се израчуна у полиномијалном времену?
- Да ли линеарно програмирање признаје алгоритме у полиномијалном времену? Ово је 9. проблем на Смаловој листи проблема.
- Која је доња граница сложености брзог Фуријеовог алгоритма трансформација? Може ли бити бржи од О(НлогН)?
- Претпоставка динамичке оптималности за раширено дрво?
- Проблем К-сервера
- Да ли X+Y сортирање може да се обави за мање од О(н2логН) времена?