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

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

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

• Равенство классов 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