Когда «X является NP-полным» подразумевает «#X является # P-полным»?

29

Пусть обозначает (решение) задачу в NP, а # X обозначает ее счетную версию.XX

При каких условиях известно, что «X является NP-полным» "#X # P-complete"?

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

Формально говоря, следует начать с задачи подсчета # определяемой функцией f : { 0 , 1 } N, а затем определить задачу решения X для входной строки s как f ( s ) 0 ?Xf:{0,1}NXsf(s)0

Тайсон Уильямс
источник
2
Вы ищете что-то большее, чем «X является NP-полным при экономном сокращении»?
Джошуа Грохов
3
@usul: Нет. Если мы отбросим предположение, что X является NP-полным, тогда двудольное сопоставление находится в P (так что определенно не экономно NP-полное при условии ), но его счетная версия # P-полная. Тем не менее, если мы действительно хотим, чтобы X был NP-завершенным, то, черт побери, я не знаю проблемы X такой, что: 1) X является NP-завершенным, 2) X не является NP-полным при экономном сокращении, и 3) #X # P-завершен. Но я действительно не думал об этом. PNP
Джошуа Грохов
13
Но есть ли проблема, которая отрицает это? то есть X не является NP-полным, а #X не является # P-полным?
Суреш Венкат
6
@YoshioOkamoto: это доказывает, что #X ∈ #P означает, что X ∈ NP . Это в неправильном направлении и пропускает проблему полноты. По сути, мы рассматриваем то, какие дополнительные требования необходимы для того, чтобы существующее сокращение «много к одному» для задач решения в NP (для произвольных проблем решения или из NP- полной проблемы) влечет за собой существование сокращение эффективного подсчета для задач в #P (для произвольных задач подсчета или из # P- полной задачи).
Ниль де Бодрап,
3
@ColinMcQuillan Это можно сформулировать в обратном порядке. Начните с задачи подсчета и определите из нее задачу решения, спрашивая, является ли результат ненулевым.
Тайсон Уильямс

Ответы:

23

Последняя статья по этому вопросу, похоже, выглядит так:

Ноам Ливне, Записка о # P-полноте отношений со свидетелями НП , Письма по обработке информации, том 109, выпуск 5, 15 февраля 2009 г., страницы 259–261 http://www.sciencedirect.com/science/article/pii/ S0020019008003141

что дает некоторые достаточные условия.

Интересно, что во введении говорится: «На сегодняшний день все известные комплекты NP имеют определяющее отношение, которое является #P complete», поэтому ответом на комментарий Суреша является «примеры не известны».

Колин Маккуиллан
источник
6

Фишер, Софи, Лейн Хемаспандра и Лин Торенвлит. «Свидетельско-изоморфные сокращения и локальный поиск». ЗАМЕЧАНИЯ ЛЕКЦИИ ПО ЧИСТОЙ И ПРИКЛАДНОЙ МАТЕМАТИКЕ (1997): 207-224.

В начале раздела 3.5 они задают следующий вопрос: «В частности, существуют ли NP-полные наборы, которые по какой-либо схеме свидетелей не #P-полные?»

LP P#P

Тайфун Пей
источник