Вот ссылка на открытую по сей день проблему: http://ru.wikipedia.org/wiki/Равенство_классов_P_и_NP
:: В конечном счете проблема P = NP состоит в следующем: если положительный ответ на какой-то вопрос можно быстро проверить (за полиномиальное время), то правда ли, что ответ на этот вопрос можно быстро найти (за полиномиальное время и используя полиномиальную память)?
Например, верно ли, что среди чисел {−2, −3, 15, 14, 7, −10, ...} есть такие, что их сумма равна 0 (задача о суммах подмножеств)? Ответ да, потому что −2 −3 + 15 −10 = 0 легко проверяется несколькими сложениями (информация, необходимая для проверки положительного ответа, называется сертификат). Следует ли отсюда, что так же легко подобрать эти числа? Проверить сертификат так же легко, как найти его? Кажется, что подобрать числа сложнее (не доказано). ::
Только мне кажется что это тупняк? Вроде как сложность подбора чисел (просто тычком пальца в небо) зависит от размера выборки. И, если мы имеем (или постулируем) лишь одно решение, то и сложность поиска ответа можно увеличивать безгранично. Или я что-то в корне понимаю не так?
