¿Problema NP-completo con un número polinómico de instancias de sí?

Tengo la impresión de que para cada problema de NP completo, para infinitos tamaños de entrada , el número de instancias sí sobre todas las entradas posibles de tamaño , es (al menos) exponencial en .$n$$n$$n$

¿Es esto cierto? ¿Se puede probar (probablemente solo bajo el supuesto de que )? ¿O podemos, quizás artificialmente, encontrar un problema en el que para todos (lo suficientemente grande) , el número de instancias sí es polinomial como máximo en ?n $P\neq NP$$n$$n$

Mi razonamiento es básicamente que, dada una instancia de sí para 3-SAT, podemos identificar el literal en cada cláusula que lo hace verdadero y reemplazar otra variable en la cláusula con otra variable, sin cambiar que sea satisfactoria. Dado que podríamos hacer eso con cada cláusula, lleva a un número exponencial de instancias de sí. Lo mismo vale para muchos otros problemas, como el camino hamiltoniano: podemos cambiar libremente los bordes que no están en el camino. Entonces razoné vagamente que, dado que la reducibilidad está involucrada donde de alguna manera deben mantenerse las soluciones, debe ser válida para todos los problemas de NP completo.

También parece sostenerse para el problema quizás NP-intermedio del isomorfismo gráfico (donde podemos aplicar libremente los mismos cambios a ambos gráficos si conocemos el mapeo). Me pregunto si también es válido para la factorización de enteros.

Un lenguaje con solo polinomios muchas instancias de sí se llama disperso . El teorema de Mahaney establece que si cualquier lenguaje NP-completo es escaso, entonces P = NP. Como la mayoría de la gente espera que P NP, parece poco probable que exista un lenguaje NP-completo con solo polinomios muchas instancias de sí.$\ne$

Es una pregunta separada si el número de instancias de sí es exponencial. (Uno podría imaginar que el número de instancias de sí podría ser más que polinomial pero menos exponencial). La conjetura de Berman-Hartmanis es relevante aquí; implica que todos los problemas de NP completo tienen exponencialmente muchas instancias de sí. La conjetura sigue siendo un problema abierto.