Нерешённые проблемы информатики
Материал из Википедии — свободной энциклопедии
 |
Эта статья предлагается к удалению.
Пояснение причин и соответствующее обсуждение вы можете найти на странице Википедия:К удалению/3 января 2016.
Пока процесс обсуждения не завершён, статью можно попытаться улучшить, однако следует воздерживаться от переименований или немотивированного удаления содержания, подробнее см. руководство к дальнейшему действию. Не снимайте пометку о выставлении на удаление до окончания обсуждения. Последнее изменение сделано участником Stannic (вклад, журналы) в 21:58 UTC (390656 минут назад). Администраторам: ссылки сюда, история, журналы, удалить. |
В этой статье приводится список нерешённых проблем информатики. В информатике проблема считается нерешённой, если эксперт в этой области считает проблему нерешённой либо если несколько экспертов расходятся во мнениях по поводу её решения.
Содержание
Вычислительная сложность[править | править вики-текст]
- Равенство классов P и NP. Проблема равенства классов P и NP является одной из семи задач тысячелетия.
- Равенство классов NC и P
- Равенство классов NP и co-NP
- Равенство классов P и BPP
- Равенство классов P и PSPACE
- Каковы взаимоотношения между классами BQP и NP?
- Существуют ли односторонние функции?
Алгоритмы[править | править вики-текст]
- Какой самый быстрый алгоритм умножения двух n-значных чисел?
- Какой самый быстрый алгоритм умножения матриц?
- Может ли быть выполнена факторизация целых чисел за полиномиальное время на классическом компьютере?
- Может ли быть вычислен дискретный логарифм за полиномиальное время на классическом компьютере?
- Может ли быть решена проблема изоморфизма графов за полиномиальное время?
- Динамическая гипотеза оптимальности для расширенных деревьев
- Проблема К-Сервера
Языки программирования[править | править вики-текст]
Сверхтьюринговые вычисления[править | править вики-текст]
Проблемы, решённые за последние десятилетия[править | править вики-текст]
 |
Этот раздел статьи ещё не написан.
Согласно замыслу одного из участников Википедии, на этом месте должен располагаться специальный раздел.
Вы можете помочь проекту, написав этот раздел. |
Источники[править | править вики-текст]
- 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.
Ссылки[править | править вики-текст]
|
||||||
