Пытаясь доказать NP-полноту

Question

Представь, у меня есть уравнение, подобное

A + B + C + D + E + F + G + H + … = некоторое значение

И каждое слагаемое имеет верхний предел

A ≤ 500, B ≤ 200, C ≤ 300, D ≤ 600, …

Если я хочу, чтобы программа определяла каждую возможную комбинацию слагаемых, была бы проблема NP-полной? Как будет выглядеть математическое доказательство?

Если нет, то как будет выглядеть эффективный алгоритм для этой проблемы?

Answer 1

Чтобы определить, является ли проблема NP завершенной, вы должны сначала выяснить, находится ли она в NP. Нам нужно создать решение вопроса из проблемы.

Если вы хотите установить ограничение на сумму без фактического определения всех комбинаций слагаемых, вопрос о решении может быть таким: Существуют ли ограничения для A, B, C... такие, что сумма составляет ≤ k? Тогда ваш сертификат может быть набором ограничений на слагаемые.

Здесь решение вопроса неясно, и сертификат не может быть проверен. Эта проблема, как она сформулирована, не в NP.