Гипотеза P против NP — одна из ключевых задач современной информатики, которая связана с пониманием границ вычислительных возможностей. 1 Она касается сравнения двух классов задач: тех, которые можно решить эффективно (P), и тех, проверку решений которых можно провести за приемлемое время (NP). 1

Суть гипотезы заключается в вопросе, может ли каждая задача из класса NP быть решена за такое же время, как и проверка её решения. 1

В криптографии многие схемы шифрования полагаются на сложность определённых задач, таких как факторизация целых чисел и дискретные логарифмы, которые, как полагают, относятся к NP, но не к P. 2 Если бы P было равно NP, эти проблемы потенциально могли бы быть решены эффективно, что поставило бы под угрозу безопасность криптографических систем. 2

В теории алгоритмов гипотеза P против NP имеет значение, поскольку затрагивает природу математической истины и пределы человеческого знания. 2 Если бы P было равно NP, это означало бы, что каждое математическое утверждение с коротким доказательством можно было бы эффективно обнаружить, что потенциально произвело бы революцию в процессе математических открытий. 2

Гипотеза была сформулирована в 1971 году и до сих пор остаётся нерешённой. 1 Большинство экспертов считают, что P не равно NP, хотя доказательств этому пока нет. 3