-полная задача с квазиполиномиальной оценкой числа решений

FewP - это класс -задач с полиномиальной оценкой числа решений (во входном размере). Там нет никакого известного Св.нут P -полные проблемы в ф х ш Р . Мне интересно, как далеко мы можем расширить это наблюдение.$NP$$NP$$fewP$

Существует ли естественная -полная проблема с квазиполиномиальной верхней оценкой числа решений (свидетелей)? Есть ли общепринятая гипотеза, которая исключает такую ​​возможность?$NP$

Естественный означает, что проблема не является искусственно созданной проблемой, чтобы ответить на вопрос (или аналогичные), и люди интересуются проблемой независимо (как определено Каве).

РЕДАКТИРОВАТЬ: Щедрость будет присуждаться за такую ​​естественную -полную проблему или разумный аргумент, исключающий существование таких проблем (используя широко принятые гипотезы теории сложности).$NP$

Мотивация: Моя интуиция заключается в том, что -полнота накладывает суперполиномиальную (или даже экспоненциальную) нижнюю границу числа свидетелей.$NP$

Это очень интересный вопрос.

Сначала уточняющее замечание. Обратите внимание, что «верхняя граница числа свидетелей» не является свойством вычислительной проблемы как таковой, но конкретного верификатора, используемого для решения задачи , так же как «верхняя граница числа состояний» не будет свойство проблемы, но решающая ее машина Тьюринга. Таким образом, высказывание « проблема N P с верхней границей числа решений» не совсем точно, и если P = N P, то у каждой задачи N P есть верификатор с любым количеством желаемых решений (включая ноль и включая все возможные строки) ,$NP$$NP$$P = NP$$NP$

Поэтому мы должны дать определение, чтобы ответить на ваш вопрос. Для , скажем, задача N P L «имеет не более s ( n ) решений», если для некоторой константы c существует O ( n c ) -временной верификатор V такой, что для каждой входной длины n и для каждый x ∈ L длины n , есть различные y 1 , … , y s ( $s : {\mathbb N} \rightarrow {\mathbb N}$$NP$$L$$s(n)$$c$$O(n^c)$$V$$n$$x \in L$$n$ длины n c такой, чтоV(x, y i )принимает для всехi, аV(x,y)отклоняет все остальныеyдлины n c .$y_1,\ldots,y_{s(n)}$$n^c$$V(x,y_i)$$i$$V(x,y)$$y$$n^c$

Все, что я могу сказать на данный момент, так это:

1. Каждый -полная проблема , которую я знаю (определяются некоторыми естественными проверяющим) имеет очевидную соответствующую # P версию -полным подсчета (с тем же проверяющим).$NP$$\#P$
2. Для любого -полным задачи , определенной с верификатор , имеющие не более р ø л у ( п ) решений (или даже 2 п о ( 1 ) решений) соответствующий счет версия , вероятно, не # Р -полная.$NP$$poly(n)$$2^{n^{o(1)}}$$\#P$

Более подробно: предположим, что является N P -полным, с верификатором V, который имеет не более O ( n c ) решений. Тогда естественный подсчет "решение" версия L , который мы определяем как$L$$NP$$V$$O(n^c)$$L$

$Count_L(x) := \text{the number of $y$ such that $V(x,y)$ accepts}$

вычислим в , то есть, функция полиномиальных по с O ( журнал п ) запросов к N P . Это потому , что решить , является ли число решений й не больше к находится в N P : свидетель, если он существует, это просто число у я «s делает V принять, что мы знаем , что в большинстве O ( п в$FP^{NP[O(\log n)]}$$O(\log n)$$NP$$x$$k$$NP$$y_i$$V$$O(n^c)$, Тогда мы можем бинарный поиск , используя эту задачу вычислить точное число решений L .$NP$$L$

Следовательно, -полная проблема такого рода не может быть распространена на # P -полную проблему обычным способом, если только # P ⊆ F P N P [ O ( log n ) ] . Это выглядит маловероятным; вся полиномиальная иерархия времени в основном рухнет до P N P [ O ( log n ) ] .$NP$$\#P$$\#P \subseteq FP^{NP[O(\log n)]}$$P^{NP[O(\log n)]}$

Если вы предполагаете в вышеприведенном, вы все равно получите маловероятные последствия. Вы бы показали, что # P можно вычислить за 2 n o ( 1 ) времени с помощью оракула N P. Например, этого более чем достаточно, чтобы доказать, что E X P N P ≠ P P, а затем E X P N P ⊄ P / p o l $s(n) = 2^{n^{o(1)}}$$\#P$$2^{n^{o(1)}}$$NP$$EXP^{NP} \neq PP$$EXP^{NP} \not\subset P/poly$, Не то, чтобы эти разделения были маловероятными, но кажется маловероятным, что они были бы доказаны с помощью алгоритма оракула времени субэкспозиции для Перманента.$NP$

Кстати, я не сказал ничего слишком проницательного здесь. В литературе почти наверняка есть такой аргумент.