# P-полная проблема, чья версия решения находится в P

14

1) Возможно ли экономное сокращение от # P-полной задачи #A до проблемы подсчета #B, когда (версия решения) A является NP-полной, а B находится в P?

Например, может ли быть экономное сокращение от #SAT до #B, когда B находится в P?

2) Если B находится в P, каковы различные возможности для сложности #B?

cc.complexity-theory complexity-classes counting-complexity marjoonjan
источник

20

$F$ $G$ $2^{8m}+1$ $4^m$ $F$ $m$ $F$ $F$ $G$

См. Главу 18 в книге Пападимитриу «Вычислительная сложность» для ясного изложения этого.

slimton
источник

7

Ответ на вопрос 2 состоит в том, что сложность задачи подсчета #B может быть в принципе чем угодно (даже необязательно вычисляемой). Точнее, ограничение на то, что версия решения находится в P, не имеет никакого значения для сложности версии подсчета. Это связано с тем, что вы можете добавить фиктивное решение к любой проблеме отношений, чтобы версия решения стала тривиальной (ответ всегда будет положительным), не изменяя сложность версии подсчета.

Цуёси Ито
источник

1

почему ты так говоришь? "(даже не обязательно вычислимый)" Ясно, что если B - это проблема решения в P, то #B находится в #P, прямо из определения класса #P! но доказательство #B также важно для # P-com, и добавление фиктивных решений не должно влиять на сложность подсчета. ты согласен?

Marjoonjan

@marjoonjan: «Понятно, что если B является проблемой решения в P, то #B находится в #P, прямо из определения класса #P». Это неверно. Кроме того, у меня создается впечатление, что вы считаете, что решение проблемы B однозначно определяет проблему подсчета #B, но это не тот случай, как я объяснил в этом ответе.

Цуёси Ито

# P-полная проблема, чья версия решения находится в P

Ответы: