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

14

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

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

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

marjoonjan
источник

Ответы:

20

FG28m+14mFmFFG

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

slimton
источник
7

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

Цуёси Ито
источник
1
почему ты так говоришь? "(даже не обязательно вычислимый)" Ясно, что если B - это проблема решения в P, то #B находится в #P, прямо из определения класса #P! но доказательство #B также важно для # P-com, и добавление фиктивных решений не должно влиять на сложность подсчета. ты согласен?
Marjoonjan
@marjoonjan: «Понятно, что если B является проблемой решения в P, то #B находится в #P, прямо из определения класса #P». Это неверно. Кроме того, у меня создается впечатление, что вы считаете, что решение проблемы B однозначно определяет проблему подсчета #B, но это не тот случай, как я объяснил в этом ответе.
Цуёси Ито