Циклопедия:Списки:Нерешённые проблемы информатики
(перенаправлено с «Нерешённые проблемы информатики»)
Перейти к навигации
Перейти к поиску
В этой статье приводится список нерешённых проблем информатики. В информатике проблема считается нерешённой, если эксперт в этой области считает проблему нерешённой либо если несколько экспертов расходятся во мнениях по поводу её решения.
Вычислительная сложность[править]
- Равенство классов 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. — С. 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.
Ссылки[править]
↑ [+] | |
---|---|
|