В статье Рамирес-Альфонсон « Сложность проблемы Фробениуса» доказана, что задача NP-полна с использованием редукций Тьюринга. Это возможно? Как именно? Я думал, что это было возможно только за полиномиальное время много одного сокращения. Есть ли какие-либо ссылки по этому поводу?
Существуют ли два разных понятия NP-твердости, даже NP-полноты? Но тогда я запутался, потому что с практической точки зрения, если я хочу показать, что моя проблема NP-трудна, что мне использовать?
Они начали описание следующим образом:
Сокращение Тьюринга за полиномиальное время от задачи к другой проблеме - это алгоритм A, который решает с помощью гипотетической подпрограммы A 'для решения , что если бы A' был алгоритмом полиномиального времени для то A был бы полиномиальным временем алгоритм для . Мы говорим, что может быть сокращен по Тьюрингу до .
Задача называется (Тьюринг) NP-трудной, если существует NP-полная задача решения , так что может быть сокращена по Тьюрингу до .P 2 P 1
И затем они используют такое сокращение Тьюринга из NP-полной задачи, чтобы показать NP-полноту некоторой другой проблемы.
источник
Все в порядке. Уменьшение Тьюринга за полиномиальное время является уменьшением Кука (как в теореме Кука-Левина), а приведение задачи NP-полного к новой задаче дает NP-твердость (как и уменьшение многочлена за полиномиальное время, сокращение AKA Карпа). Действительно, сокращения Карпа просто ограничены сокращениями Тьюринга в любом случае.
В чем они отличаются (в отношении этого вопроса) - в членстве. Сведение Карпа от проблемы к проблеме в NP показывает, что первое находится в NP. Сокращение Кука в том же направлении не делает.
источник