У меня возникли некоторые трудности с пониманием сокращений с использованием задач NP, и я хотел бы получить разъяснения. Рассмотрим следующую проблему:
Show that the following problem is NP-Complete by designing
a polynomial-time reduction algorithm from an already known
NP-Complete problem.
Problem: Given an undirected graph G=(V,E) and integer k,
test whether G has a cycle of length k.
Я знаю, что есть другие темы, касающиеся этого предмета, но я все еще не уверен, что понимаю, как можно было бы сделать такие сокращения.
Насколько я понимаю, именно так вы бы подошли к такой проблеме.
- Предположим, что данная задача может быть решена за полиномиальное время.
- Используйте данную задачу, чтобы решить задачу, которая, как мы знаем, является NP-сложной за полиномиальное время.
- Это создает противоречие, поэтому предположение должно быть неверным
- Таким образом, данная задача не должна решаться за полиномиальное время
Итак, для такой проблемы, будет ли это правильным подходом?
- Если мы выберем k как длину гамильтонова цикла в графе (при условии, что он есть), это означает, что эту задачу можно использовать для нахождения гамильтонова цикла в графе.
- Поскольку мы можем найти гамильтонов цикл только за NP-время, эта задача также должна быть разрешима только за NP-время.
