Вы на правильном пути, но нужно сделать еще немного, чтобы показать, что проблема А на самом деле сложная.Если вы уже доказали, что проблема A находится в NP (переформулируйте как проблему решения, опишите сертификат «да» и покажите, что его можно проверить за полиномиальное время), то вы должны показать, что если бы вы гипотетически нашлиалгоритм, который решает проблему A за полиномиальное время, то этот алгоритм можно использовать и для решения любой задачи SAT за полиномиальное время.
Это показывает, что ваша проблема требует, чтобы вы решали SAT (а также другие возможные входные данные для задачи A) за полиномиальное время, и, поскольку SAT еще предстоит решить за полиномиальное время, вы можете объяснить тому, кто спрашиваетвам решить проблему, что это необоснованный запрос.Чтобы показать это, найдите способ преобразовать SAT во входные данные для вашей задачи A (подумайте, как преобразовать ребра и вершины во входные данные задачи A).
Теперь покажите, что это преобразование из SAT в задачу A выполняется за полиномиальное время, а затем покажите, что ответ из задачи A можно преобразовать обратно в ответ для SAT (опять же, за полиномиальное время).Наконец, обязательно объясните, что ответ на проблему A эквивалентен ответу на SAT (ответ на SAT правильный, если ответ на задачу A правильный).
Для всех этих этапов обработайтегипотетический алгоритм для задачи A как черный ящик, который волшебным образом решает проблему за полиномиальное время.