-problema completo con cuasi-polinomio unido en el número de soluciones

FewP es la clase de problemas de $NP$ con polinomios unidos en el número de soluciones (en el tamaño de entrada). Hay no se conoce $NP$ problema -Complete en $fewP$ . Me interesa hasta dónde podemos extender esta observación.

¿Existe algún problema natural de $NP$ completo con el límite superior cuasi-polinomial en el número de soluciones (testigos)? ¿Existe una conjetura ampliamente aceptada que descartaría tal posibilidad?

Natural significa que el problema no es un problema artificialmente inventado para responder la pregunta (o preguntas similares) y que las personas están interesadas en el problema de forma independiente (como lo define Kaveh).

EDITAR: La recompensa se otorgará a dicho problema natural de $NP$ completo o un argumento razonable que descarte la existencia de tales problemas (utilizando conjeturas teóricas de complejidad ampliamente aceptadas).

Motivación: Mi intuición es que la completitud de $NP$ impone un límite inferior superpolinomial (o incluso exponencial) en el número de testigos.

Esta es una pregunta muy interesante.

Primero, un comentario aclaratorio. Tenga en cuenta que el "límite superior en el número de testigos" no es una propiedad de un problema computacional per se, sino de un verificador particular utilizado para decidir un problema N P , así como un "límite superior en el número de estados" no sería un propiedad de un problema pero de una máquina de Turing que lo decide. Por lo tanto, decir " Problema N P con límite superior en el número de soluciones" no es del todo exacto, y si P = N P, entonces cada problema N P tiene un verificador con cualquier número de soluciones deseadas (incluyendo cero e incluyendo todas las cadenas posibles) .$NP$$NP$$P = NP$$NP$

Entonces tenemos que hacer una definición, para abordar su pregunta. Para s : N → N , supongamos que un problema N P L "tiene como máximo soluciones s ( n ) " si para alguna constante c hay un verificador de tiempo O ( n c ) V tal que, para cada longitud de entrada n y para cada x ∈ L de longitud n , hay distintos y 1 , ... , y s ( $s : {\mathbb N} \rightarrow {\mathbb N}$$NP$$L$$s(n)$$c$$O(n^c)$$V$$n$$x \in L$$n$) de longitud n c de modo queV(x, y i )acepte todoi, yV(x,y)rechace todos los demásyde longitud n c .$y_1,\ldots,y_{s(n)}$$n^c$$V(x,y_i)$$i$$V(x,y)$$y$$n^c$

Todo lo que creo que puedo decir en este momento es esto:

1. Cada problema de N P -completo que conozco (definido por algún verificador natural) tiene una versión de recuento completa # P- obvia correspondiente (con el mismo verificador).$NP$$\#P$
2. Para cualquier problema N P- completo definido con un verificador que tenga como máximo soluciones p o l y ( n ) (o incluso 2 n o ( 1 ) soluciones) la versión de conteo correspondiente probablemente no sea # P -complete.$NP$$poly(n)$$2^{n^{o(1)}}$$\#P$

Más detalles: Suponga que L es N P -completo, con un verificador V que tiene como máximo O ( n c ) soluciones. Luego, la versión de "decisión" de conteo natural de L , que definimos como$L$$NP$$V$$O(n^c)$$L$

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

es computable en F P N P [ O ( log n ) ] , es decir, una función polytime con O ( log n ) consultas a N P . Esto se debe a que decidir si el número de soluciones para x es como máximo k está en N P : el testigo, si existe, es simplemente el número de y estoy haciendo que V acepte, que sabemos que es como máximo O ( n c$FP^{NP[O(\log n)]}$$O(\log n)$$NP$$x$$k$$NP$$y_i$$V$$O(n^c)$. Entonces podemos búsqueda binaria utilizando este N P problema para calcular el número exacto de soluciones a L .$NP$$L$

Por lo tanto, un problema completo de N P de este tipo no puede extenderse a un problema completo de # P de la manera habitual, a menos que # P ⊆ F P N P [ O ( log n ) ] . Esto parece poco probable; toda la jerarquía de tiempo polinomial básicamente colapsaría a P N P [ O ( log n ) ] .$NP$$\#P$$\#P \subseteq FP^{NP[O(\log n)]}$$P^{NP[O(\log n)]}$

Si asume s ( n ) = 2 n o ( 1 ) en lo anterior, aún obtendría una consecuencia poco probable. Se podría demostrar que # P puede calcularse de 2 n O ( 1 ) tiempo con una N P oráculo. Eso es más que suficiente para demostrar, por ejemplo, que E X P N P ≠ P P y posteriormente 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$. No es que estas separaciones son poco probables, pero parece poco probable que estarían probaron dando un tiempo subexp N P algoritmo -oracle para la Permanente.$NP$

Por cierto, no he dicho nada demasiado perspicaz aquí. Es casi seguro que hay un argumento como este en la literatura.