Нерешённые проблемы информатики

В этой статье приводится список нерешённых проблем информатики. В информатике проблема считается нерешенной, если эксперт в этой области считает проблему нерешенной, либо если несколько экспертов расходятся во мнениях по поводу её решения.

Вычислительная сложность

• Равенство классов P и NP. Проблема равенства классов P и NP является одной из семи задач тысячелетия.
• Равенство классов NC и P
• Равенство классов NP и co-NP
• Равенство классов P и BPP
• Равенство классов P и PSPACE
• Каковы взаимоотношения между классами BQP и NP?
• Существуют ли односторонние функции?

Алгоритмы

• Какой самый быстрый алгоритм умножения двух n-значных чисел?
• Какой самый быстрый алгоритм умножения матриц?
• Может ли быть выполнена факторизация целых чисел за полиномиальное время на классическом компьютере?
• Может ли быть вычислен дискретный логарифм за полиномиальное время на классическом компьютере?
• Может ли быть решена проблема изоморфизма графов за полиномиальное время?
• Динамическая гипотеза оптимальности для расширенных деревьев
• Проблема К-Сервера

Языки программирования

• Проблема POPLmark

Проблемы, решённые за последние десятилетия

Этот раздел статьи ещё не написан. Согласно замыслу одного из участников Википедии, на этом месте должен располагаться специальный раздел. Вы можете помочь проекту, написав этот раздел.

Ссылки

• Major unsolved problems in theoretical computer science.
• Open problems around exact algorithms
• Challenges for Theoretical Computer Science
• The Open Problems Project
• The RTA list of open problems
• The TLCA List of Open Problems