Всем нам давно известна теория уравнения P и NP: заключается она в следующем:
P = NP. Задача впервые была предложена в 1971 году. Проще говоря, проблема равенства P = NP состоит в следующем: если положительный ответ на какой-то вопрос можно быстро проверить (за полиномиальное время), то правда ли, что ответ на этот вопрос можно быстро найти.
Например, верно ли, что среди чисел {−2, −3, 15, 14, 7, −10, …} есть такие, что их сумма равна 0 (задача о суммах подмножеств)? Ответ да, потому что −2 −3 + 15 −10 = 0 легко проверяется несколькими сложениями (информация, необходимая для проверки положительного ответа, называется сертификатом). Следует ли отсюда, что так же легко подобрать эти числа? Проверить сертификат так же легко, как найти его? Кажется, что подобрать числа сложнее, но это не доказано.
Ну вот и пришло время это доказать,ну что начнем:
P≠NP
По причине того что в проверке идёт единственный шаг это проверка самого сертификата,а при поиске решения идёт несколько шагов, поиск алгоритма на котором будет основан сертификат,где следующим при поиске этого алгоритма вступает расчет количества возможных его вариантов,после чего идёт их проверка(то есть работоспособность сертификатов),и чем больше вариантов алгоритмов тем больше требуется времени для проверки сертификатов.
