У нас было несколько вопросов о связи сокращений Кука и Карпа . Понятно, что сокращения Кука (сокращения Тьюринга за полиномиальное время) не определяют то же понятие NP-полноты, что и сокращения Карпа (сокращения многозначного за полиномиальное время), которые обычно используются. В частности, уменьшение Кука не может отделить NP от co-NP, даже если P NP. Поэтому мы не должны использовать сокращения Кука в типичных доказательствах сокращения.
Теперь студенты нашли рецензируемую работу [1], в которой используется уменьшение Кука, чтобы показать, что проблема NP-сложная. Я не дал им полную оценку за сокращение, которое они взяли оттуда, но мне интересно.
Поскольку сокращение Кука сделать определение аналогичного понятия твердости , как сокращение Карпа, я чувствую , что они должны быть в состоянии отделить Р от NPC соответственно. со-NPC, предполагая, что P NP. В частности, (что-то вроде) должно быть верно следующее:
.
Важным самородком является то, что так что отмеченная выше нечувствительность обходится. Теперь мы «знаем» - по определению NPC - что .L 2 ≤ K a r p L 1
Как заметил Вор , это не так просто (адаптированные обозначения):
Предположим, что , то по определению, для всех языков мы иметь ; и если приведенное выше утверждение верно, то и, следовательно, который все еще остается открытым вопросом.
Могут быть и другие различия между двумя NPC, кроме совместной NP.
В противном случае, существуют ли какие-либо известные (нетривиальные) критерии для случая, когда уменьшение Кука подразумевает твердость по Карпу-NP, т.е. знаем ли мы предикаты с
?
- О сложности множественного выравнивания последовательностей Л. Вана и Т. Цзян (1994)
Ответы:
Это, в общем, открытая проблема TCS, которая является предметом продолжающегося исследования того, являются ли & точные условия сокращений Кука и Карпа эквивалентными и, по-видимому, тесно связано с открытым вопросом NP =? coNP и другими разделениями классов сложности, например, E =? NE (относительно редких языков).
Вот две исследовательские работы на эту тему и дальнейшие ссылки на tcs.se через аналогичный вопрос:
Кук и Карп всегда одинаковы? Бейгель, Фортноу
Кук против Карпа-Левина: разделяющие понятия полноты, если NP не маленький (1995) Lutz, Mayordomo
много сокращений одного против сокращений Тьюринга для определения NPC , tcs.se
источник
В общем, для того, чтобы механически превратить задачу, полную по Каку, в проблему, полную по Карпу, в самом языке должно быть что-то особенное .
Например, даже сильно ограниченная версия сокращения Кука, а именно отрицательное сокращение (сведение к одному экземпляру, как это делает Karp, запрос ответа, затем отрицание), потребовала бы чего-то особенного в языке чтобы легко превратить его в стандартное сокращение Karp.L
Можно сказать, что если обладает следующим свойством :L
Для любого экземпляра мы можем за полиномиальное время произвести , такое что .x x′=f(x) L(x)≠L(x′)
Таким образом, мы можем получить стандартное уменьшение Карпа, сначала уменьшив до отрицательное, а затем вывести .g(x) f(g(x))
Как видите, эти свойства обычно не видны в теории сложности, теории вычислимости. В заключение, вряд ли удастся превратить Кука в Карпа.
источник