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

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

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

Алгоритмы

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

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

Ссылки

• 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