Если положительный ответ на какой-то вопрос можно быстро проверить (за полиномиальное время), то правда ли, что ответ на этот вопрос можно быстро найти (за полиномиальное время и используя полиномиальную память) ? Другими словами, действительно ли решение задачи проверить не легче, чем его отыскать?

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

Question

Информатика

Алексей

17 октября, 04:21

Если положительный ответ на какой-то вопрос можно быстро проверить (за полиномиальное время), то правда ли, что ответ на этот вопрос можно быстро найти (за полиномиальное время и используя полиномиальную память) ? Другими словами, действительно ли решение задачи проверить не легче, чем его отыскать?

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

+4

Ответы (1)

Знаете ответ?

Геннадия · Answer 1

Нет, например задачи NP - класса 3-SAT и 3-NCF, также задача факторизации за ф-ию от длины. Решение - экспонента, а проверка ответа - линейная (полином)