Некоторые нерешённые проблемы в теории сложности вычислений:

• Проблема P и NP. 35 Связана с классификацией вычислительных задач на основе присущей им сложности. 5 Вопрос в том, можно ли быстро решить каждую задачу, для которой можно быстро проверить правильность решения. 5
• Существование матриц Адамара определённых порядков. 5 Например, гипотеза Адамара ставит вопрос о том, существует ли матрица Адамара порядка 4k для каждого положительного целого числа k. 5
• Проблема развязывания узла. 5 Заключается в том, чтобы алгоритмически определить, можно ли превратить узел в простой круг без завязок. 5
• Оценка сложности вычисления решений систем уравнений. 4 В частности, когда решение не выписывается конечной комбинацией известных трансцендентных функций. 4
• Построение алгоритмов вычисления широкого класса функций с оценкой битовой сложности, близкой к оптимальной. 4

Кроме того, до сих пор не завершено построение теории сложности вычислений, включая основные определения и понятия. 4