Если положительный ответ на какой-то вопрос можно быстро проверить (за полиномиальное время), то правда ли, что ответ на этот вопрос можно быстро найти (за полиномиальное время и используя полиномиальную память)? другими словами, действительно ли решение проверить не легче, чем его отыскать? например, верно ли, что среди чисел {−2, −3, 15, 14, 7, −10, …} есть такие, что их сумма равна 0 ( о суммах подмножеств)? ответ да, потому что −2 −3 + 15 −10 = 0 легко проверяется несколькими сложениями (информация, необходимая для проверки положительного ответа, называется сертификатом). следует ли отсюда, что так же легко подобрать эти числа?
