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

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

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

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

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

cc.complexity-theory np-hardness counting-complexity Тайсон Уильямс
источник

Вы ищете что-то большее, чем «X является NP-полным при экономном сокращении»?

Джошуа Грохов

@usul: Нет. Если мы отбросим предположение, что X является NP-полным, тогда двудольное сопоставление находится в P (так что определенно не экономно NP-полное при условии

), но его счетная версия # P-полная. Тем не менее, если мы действительно хотим, чтобы X был NP-завершенным, то, черт побери, я не знаю проблемы X такой, что: 1) X является NP-завершенным, 2) X не является NP-полным при экономном сокращении, и 3) #X # P-завершен. Но я действительно не думал об этом.

P \neq N P

$P \neq NP$

Джошуа Грохов

Но есть ли проблема, которая отрицает это? то есть X не является NP-полным, а #X не является # P-полным?

Суреш Венкат

@YoshioOkamoto: это доказывает, что #X ∈ #P означает, что X ∈ NP . Это в неправильном направлении и пропускает проблему полноты. По сути, мы рассматриваем то, какие дополнительные требования необходимы для того, чтобы существующее сокращение «много к одному» для задач решения в NP (для произвольных проблем решения или из NP- полной проблемы) влечет за собой существование сокращение эффективного подсчета для задач в #P (для произвольных задач подсчета или из # P- полной задачи).

Ниль де Бодрап,

@ColinMcQuillan Это можно сформулировать в обратном порядке. Начните с задачи подсчета и определите из нее задачу решения, спрашивая, является ли результат ненулевым.

Тайсон Уильямс

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

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

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

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

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

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

Ответы: