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

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

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

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

Алгоритмы

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

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

• Проблема POPLmark

Источники

• 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.

Ссылки

• Major unsolved problems in theoretical computer science.