Нерешённые проблемы информатики
 |
Эта статья предлагается к удалению.
Пояснение причин и соответствующее обсуждение вы можете найти на странице Википедия:К удалению/21 ноября 2016.
Пока процесс обсуждения не завершён, статью можно попытаться улучшить, однако следует воздерживаться от переименований или немотивированного удаления содержания, подробнее см. руководство к дальнейшему действию. Не снимайте пометку о выставлении на удаление до окончания обсуждения. Последнее изменение сделано участником Concomberjvck (вклад, журналы) в 19:17, 10 сентября 2017 (UTC; около 15 дней назад). Администраторам: ссылки сюда, история, журналы, удалить. |
В этой статье приводится список нерешённых проблем информатики. В информатике проблема считается нерешённой, если эксперт в этой области считает проблему нерешённой либо если несколько экспертов расходятся во мнениях по поводу её решения.
Содержание
Вычислительная сложность[править | править вики-текст]
- Равенство классов 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.
- The Open Problems Project.
- The RTA list of open problems.
- The TLCA List of Open Problems.
