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

250

404

Посмотреть ответы 2

Ответы на вопрос:

INNADANILOVA

Информатика

4,8(71 оценок)

Нет, например np - класса 3-sat и 3-ncf, также факторизации за ф-ию от длины. решение - экспонента, а проверка ответа - линейная(полином)

Лаура2205200

Информатика

4,5(14 оценок)

ответ:

м+с =114,да сложно

ответ синий

Задай свой вопрос

Как otvet5GPT работает?

otvet5GPT использует большую языковую модель вместе с базой данных GPT для обеспечения высококачественных образовательных результатов. otvet5GPT действует как доступный академический ресурс вне класса.
Сколько это стоит?

Проект находиться на стадии тестирования и все услуги бесплатны.
Могу ли я использовать otvet5GPT в школе?

Конечно! Нейросеть может помочь вам делать конспекты лекций, придумывать идеи в классе и многое другое!
В чем отличия от ChatGPT?

otvet5GPT черпает академические источники из собственной базы данных и предназначен специально для студентов. otvet5GPT также адаптируется к вашему стилю письма, предоставляя ряд образовательных инструментов, предназначенных для улучшения обучения.