Задача на счет (сложность)

В теории сложности вычислений и теории вычислимости задача подсчета является разновидностью вычислительной задачи . Если R — задача поиска , то

c_{R}(x)=\vert \{y\mid R(x,y)\}\vert \,

– соответствующая считающая функция и

\#R=\{(x,y)\mid y\leq c_{R}(x)\}

обозначает соответствующую проблему решения.

Обратите внимание, что c _R — это проблема поиска, тогда как # R — это проблема принятия решения, однако c _R может быть сведена C Cook к # R (для соответствующего C ) с использованием двоичного поиска (причина # R определяется так, как она есть, а не чем быть графиком c _R , это сделать возможным этот двоичный поиск).

Класс сложности подсчета [ править ]

Точно так же, как NP имеет NP-полные проблемы посредством редукций «многие единицы» , #P имеет #P-полные проблемы посредством экономных редукций , преобразований задач, которые сохраняют количество решений. ^[1]

См. также [ править ]

ГэпП

Ссылки [ править ]

^ Барак, Вооз (весна 2006 г.). «Сложность подсчета» (PDF) . Принстонский университет .

Внешние ссылки [ править ]

П ≟ НП

Эта теоретической информатикой, статья, связанная с незавершена . Вы можете помочь Википедии, расширив ее .

[1] Барак, Вооз (весна 2006 г.). «Сложность подсчета» (PDF) . Принстонский университет .

[1]