Причина, по которой это не автоматическая теорема о том, что «решение сложно, подразумевает, что счет сложен» состоит в том, что эти два утверждения используют разные определения «трудно».
Решить проблему сложно, если она является NP- полной при многочленном сокращении много-один (сокращённое Карп, сокращённое отображение за полиномиальное время).
Проблема с подсчетом является сложной, если она # P- завершена при сокращениях Тьюринга за полиномиальное время (иначе как при уменьшении Кука).
Таким образом, если проблема решения является NP- неполной, мы знаем, что соответствующая проблема подсчета является NP- трудной, но это не определение того, что представляет собой сложная проблема подсчета. Будучи #P -полным , кажется, гораздо более сильное утверждение , чем просто NP -трудной - Тода показал , что #P -полных проблемы трудно для всей полиномиальной иерархии при рандомизированных сокращений , так как класс сложности, #P чувствует себя гораздо ближе до PSPACE чем на НП .
Движение в направлении , противоположном, это явно верно , что, если проблема подсчета легко в том смысле, что в ФП , то задача решения в P . В конце концов, если вы можете эффективно рассчитывать, вы можете точно сказать, если ответ ненулевой. Однако то, что версия для подсчета «не сложная» (т. Е. Не # P- завершенная), не означает, что она «легкая» (т. Е. В FP ). Теорема Ладнера распространяется на #P, поэтому, если FP≠** # P ** тогда существует бесконечная иерархия различных классов сложности между ними, поэтому наша «не сложная» задача подсчета может быть полной для любого из этих классов и, следовательно, не может быть «легкой» (в FP ).
Сказав это, я не думаю, что у нас есть какие-либо контрпримеры к предположению, что проблема решения, являющаяся NP- полной, означает, что версия для подсчета является # P- полной. Итак, это не теорема, но это эмпирически верно.
