Нерешённые проблемы информатики
Стабильная версия была проверена 7 марта 2018. Имеются непроверенные изменения в шаблонах или файлах.
Эта статья предлагается к удалению. Пояснение причин и соответствующее обсуждение вы можете найти на странице Википедия:К удалению/21 ноября 2016. Пока процесс обсуждения не завершён, статью можно попытаться улучшить, однако следует воздерживаться от переименований или немотивированного удаления содержания, подробнее см. руководство к дальнейшему действию. Не снимайте пометку о выставлении на удаление до окончания обсуждения. Последнее изменение сделано участником InternetArchiveBot (вклад, журналы) в 02:38, 7 марта 2018 (UTC; около 50 дней назад). Администраторам: ссылки сюда, история, журналы, удалить. |
В этой статье приводится список нерешённых проблем информатики. В информатике проблема считается нерешённой, если эксперт в этой области считает проблему нерешённой либо если несколько экспертов расходятся во мнениях по поводу её решения.
Содержание
Вычислительная сложность[править | править код]
- Равенство классов P и NP. Проблема равенства классов P и NP является одной из семи задач тысячелетия.
- Равенство классов NC и P
- Равенство классов NP и co-NP
- Равенство классов P и BPP
- Равенство классов P и PSPACE
- Каковы взаимоотношения между классами BQP и NP?
- Существуют ли односторонние функции?
Алгоритмы[править | править код]
- Какой самый быстрый алгоритм умножения двух n-значных чисел?
- Какой самый быстрый алгоритм умножения матриц?
- Может ли быть выполнена факторизация целых чисел за полиномиальное время на классическом компьютере?
- Может ли быть вычислен дискретный логарифм за полиномиальное время на классическом компьютере?
- Может ли быть решена проблема изоморфизма графов за полиномиальное время?
- Динамическая гипотеза оптимальности для расширенных деревьев
- Проблема К-Сервера
Языки программирования[править | править код]
Сверхтьюринговые вычисления[править | править код]
Проблемы, решённые за последние десятилетия[править | править код]
Этот раздел статьи ещё не написан. Согласно замыслу одного из участников Википедии, на этом месте должен располагаться специальный раздел. Вы можете помочь проекту, написав этот раздел. Эта отметка установлена 30 ноября 2016 года. |
Источники[править | править код]
- James Aspnes; Costas Busch; Shlomi Dolev; Panagiota Fatourou; Chryssis Georgiou; Alex Shvartsman; Paul Spirakis; Roger Wattenhofer Eight open problems in distributed computing (англ.) // Bulletin of the European Association for Theoretical Computer Science. — 2006. — Vol. 90. — P. 109-126.
- Gerhard J. Woeginger Open problems around exact algorithms // Discrete Applied Mathematics. — 2008.
- Challenges for Theoretical Computer Science. Архивировано 4 ноября 2013 года.
- The Open Problems Project. (недоступная ссылка)
- The RTA list of open problems. Архивировано 15 мая 2013 года.
- The TLCA List of Open Problems.