¿Existe un problema de NP completo, de modo que la versión de decisión de su problema de conteo no sea PP completo?

Una vez que arreglamos un verificador determinista de tiempo polinomial V (entrada, certificado), su problema NP correspondiente es la pregunta: para esta entrada, ¿existe un certificado (tamaño polinómico) tal que V (entrada, certificado) devuelva Verdadero?

El problema de conteo asociado (clase #P) es: ¿Cuántos certificados existen de modo que V (entrada, certificado) devuelva Verdadero?

#P no es una clase de "problemas de decisión", sino una clase de problemas de conteo. La clase tradicional de "problemas de decisión" más cercana es PP, que tiene problemas de forma: ¿La mayoría de los certificados dan como resultado que V (entrada, certificado) devuelva Verdadero?

Estoy interesado en la versión de decisión del problema de conteo asociado con un cierto problema NP-completo + verificador, que sería: Dada la instancia de entrada y un número entero positivo K: ¿Hay al menos K certificados diferentes tales que V (entrada, certificado) devuelve True?

Este problema de decisión es claramente equivalente a la versión de conteo (a través de una búsqueda binaria). Si no me equivoco, la clase de todas estas "versiones de decisión de los problemas de conteo asociados con problemas NP" es exactamente tan difícil como PP ya que:

1) Cualquiera de estos problemas de "decisión de conteo" puede reformularse como otro problema mayoritario, eligiendo una definición de verificador ad-hoc en la que muchos certificados se consideren verdaderos o falsos de forma manual, de modo que haya al menos K certificados verdaderos en el original si y solo si la mayoría es Verdadera en el problema resultante. Solo como un ejemplo simple para ilustrar la idea de reducción, si hay 8 posibles certificados, y queremos saber si hay al menos 3 Verdaderos, podríamos proponer un verificador diferente que tenga 11 posibles certificados: para los 8 originales solo comprueba normalmente, y para los otros tres inmediatamente devuelve True sin mirar la entrada. Como la mayoría de 11 es 6, este nuevo verificador acepta la mayoría de los certificados exactamente si el original acepta al menos 3.

Por lo tanto, todos estos problemas están en PP.

2) La versión correspondiente de "decisión de conteo" para cualquier problema de PP completo será obviamente difícil de PP, ya que resolver el problema de la mayoría original es simplemente resolver el problema $(input, \left \lfloor \frac{ totalCertificates}{2} \right \rfloor + 1)$problema. Por lo tanto, tales problemas son PP-completos.

Así que ahora, por fin, puedo formular claramente mi pregunta, que es una "versión más sofisticada" de la misma idea mostrada en MAX, las variantes MAJ de problemas completos de NP :

¿Hay algún problema de NP completo tal que la versión de decisión de su problema de conteo (que está en PP) no sea PP-complete?

Por ejemplo, en el caso de Subset-Sum, el problema de decisión asociado que me interesa sería: ¿Hay al menos K subconjuntos no vacíos de suma cero?

Como K es gratuito y no se limita a estar cerca de la mitad de los certificados, el argumento de la otra respuesta no se aplica.

Al formular su pregunta en términos más precisos, pregunta si se cumple el siguiente reclamo:

$* \hspace{1mm} R(x,y) \text{ is an NP-complete relation}\Rightarrow count_R \text{ is PP-complete}$

Dónde $count_R$ se define de la siguiente manera:

$count_R=\left\{(x,k) \big| \hspace{1mm} \left\lvert\left\{y : R(x,y)\right\}\right\rvert\ge k\right\}$.

Llamamos una relación $R(x,y)$ NP-complete si es computable en tiempo polinómico y el lenguaje que define $L_R=\left\{x | \exists y \hspace{1mm} R(x,y)=1\right\}$ es NP-completo.

Hablamos en términos de relaciones, ya que, como mencionó, la versión de conteo debe definirse en relación con algún verificador específico.

Parece que esta es una pregunta abierta, ya que (*) implica:

$** \hspace{1mm} R(x,y) \text{ is an NP-complete relation}\Rightarrow \#R\text{ is #P-complete}$

Dónde $\#R(x)=\left\lvert \left\{y : R(x,y)\right\} \right\rvert$.

Para ver por qué * implica lo anterior, dejemos $R(x,y)$ser alguna relación NP-completa. Utilizando (*),$count_R$ es PP completo, entonces $count_{\text{SAT}}\le_p count_R$. En ese caso,$\#SAT\in\mathsf{FP}^{\# R}$ y por lo tanto $\#R$ es $\# P$-completo (use la búsqueda binaria, donde en cada corte aplica la reducción de $count_{\text{SAT}}$ a $count_R$ y consultar el $\#R$ oráculo sobre el resultado).

Que yo sepa, (**) está actualmente abierto. Vea esta pregunta relacionada de cstheory. También relacionado .