Словарь
Теория сложности вычислений
Раздел теоретической информатики, который выясняет, сколько времени, памяти и других ресурсов нужно для решения задач, и делит задачи на классы сложности. Главный открытый вопрос этой теории — «P против NP»: можно ли любую задачу, решение которой быстро проверяется, так же быстро решить. От ответа на этот вопрос зависит, например, надёжность криптографии.