Можем ли мы построить сокращение Карпа из уменьшения Кука между проблемами NP?

10

У нас было несколько вопросов о связи сокращений Кука и Карпа . Понятно, что сокращения Кука (сокращения Тьюринга за полиномиальное время) не определяют то же понятие NP-полноты, что и сокращения Карпа (сокращения многозначного за полиномиальное время), которые обычно используются. В частности, уменьшение Кука не может отделить NP от co-NP, даже если P NP. Поэтому мы не должны использовать сокращения Кука в типичных доказательствах сокращения.

Теперь студенты нашли рецензируемую работу [1], в которой используется уменьшение Кука, чтобы показать, что проблема NP-сложная. Я не дал им полную оценку за сокращение, которое они взяли оттуда, но мне интересно.

Поскольку сокращение Кука сделать определение аналогичного понятия твердости , как сокращение Карпа, я чувствую , что они должны быть в состоянии отделить Р от NPC соответственно. со-NPC, предполагая, что P NP. В частности, (что-то вроде) должно быть верно следующее:

L1NP,L2NPCKarp,L2CookL1L1NPCKarp .

Важным самородком является то, что так что отмеченная выше нечувствительность обходится. Теперь мы «знаем» - по определению NPC - что .L 2 K a r p L 1L1NPL2KarpL1

Как заметил Вор , это не так просто (адаптированные обозначения):

Предположим, что , то по определению, для всех языков мы иметь ; и если приведенное выше утверждение верно, то и, следовательно, который все еще остается открытым вопросом.L1NPCCookL2NPCKarpNPL2CookL1L1NPCKarpNPCKarp=NPCCook

Могут быть и другие различия между двумя NPC, кроме совместной NP.

В противном случае, существуют ли какие-либо известные (нетривиальные) критерии для случая, когда уменьшение Кука подразумевает твердость по Карпу-NP, т.е. знаем ли мы предикаты сP

L2NPCKarp,L2CookL1,P(L1,L2)L1NPCKarp ?


  1. О сложности множественного выравнивания последовательностей Л. Вана и Т. Цзян (1994)
Рафаэль
источник
Ваш вопрос, если ? NPCKarp=NPCCookNP
Альберт Хендрикс
@AlbertHendriks Похоже, но не то же самое. Я прошу предикат который ваш вариант должен установить на « » (см. Первую часть вопроса), т.е. если есть результаты с сильнее, чем NP-членство. L 1N P PPL1NPP
Рафаэль

Ответы:

4

Это, в общем, открытая проблема TCS, которая является предметом продолжающегося исследования того, являются ли & точные условия сокращений Кука и Карпа эквивалентными и, по-видимому, тесно связано с открытым вопросом NP =? coNP и другими разделениями классов сложности, например, E =? NE (относительно редких языков).

Вот две исследовательские работы на эту тему и дальнейшие ссылки на tcs.se через аналогичный вопрос:

ВЗН
источник
Я не ищу точное отношение.
Рафаэль
1

В общем, для того, чтобы механически превратить задачу, полную по Каку, в проблему, полную по Карпу, в самом языке должно быть что-то особенное .

Например, даже сильно ограниченная версия сокращения Кука, а именно отрицательное сокращение (сведение к одному экземпляру, как это делает Karp, запрос ответа, затем отрицание), потребовала бы чего-то особенного в языке чтобы легко превратить его в стандартное сокращение Karp.L

Можно сказать, что если обладает следующим свойством :L

Для любого экземпляра мы можем за полиномиальное время произвести , такое что .xx=f(x)L(x)L(x)

Таким образом, мы можем получить стандартное уменьшение Карпа, сначала уменьшив до отрицательное, а затем вывести .g(x)f(g(x))

Как видите, эти свойства обычно не видны в теории сложности, теории вычислимости. В заключение, вряд ли удастся превратить Кука в Карпа.

Тхин Д. Нгуен
источник