Скажем, вам задана задача комбинаторной оптимизации A. Предположим, что WLOG представляет собой проблему клики.
Как я могу показать, что если клика NP-полная, то версия решения клики NP-полна, где версия решения, конечно же, является следующей проблемой B: существует ли клика размера, равного k?
Я думаю, что имею в виду интуицию, но не уверен, достаточно ли ее в качестве доказательства:
Шаг I:
если мне дан набор вершин C размера k, я могу за полиномиальное время проверить, что существует клика размера k (при условии, что ответ на вопрос B положительный, т. е. существует клика размера k). Следовательно, B находится в NP.
Шаг II: уменьшить A до B.
-Поскольку A запрашивает клику максимального размера, мы можем разбить проблему на части, B1: существует ли клика размера 1?, ..., BN: существует ли клика размера N?
-Если A разрешима, скажем, существует клика размера k*, то на каждое Bk, k=1,...,N можно легко ответить, сравнив k с k*
-Если все Bks разрешимы, мы можем сказать, каков максимальный размер клики.
Я действительно не уверен, что это сокращение, хотя оно происходит за полиномиальное время. Возможно, потому что одна проблема разбивается на много проблем. Более того, я не уверен, что должен использовать слово «все» выше.
Спасибо за помощь! :)
