Problema NP-completo com um número polinomial de instâncias sim?

Tenho a impressão de que, para todo problema NP-completo, para infinitos tamanhos de entrada , o número de instâncias yes em todas as entradas possíveis de tamanho é (pelo menos) exponencial em .$n$$n$$n$

Isso é verdade? Isso pode ser comprovado (provavelmente apenas sob a suposição de que )? Ou podemos, talvez artificialmente, encontrar um problema em que para todos (grande o suficiente) , o número de instâncias sim é no máximo polinomial em ?$P\neq NP$$n$$n$

Meu raciocínio é basicamente que, dada uma instância yes para 3-SAT, podemos identificar o literal em cada cláusula que a torna verdadeira e substituir outra variável na cláusula por outra variável, sem alterar a satisfação. Como poderíamos fazer isso com cada cláusula, isso leva a um número exponencial de instâncias yes. O mesmo vale para muitos outros problemas, como o caminho hamiltoniano: podemos mudar livremente as arestas que não estão no caminho. Em seguida, raciocino vagamente que, uma vez que a redutibilidade está envolvida, onde, de alguma maneira, as soluções devem ser mantidas, ela deve valer para todos os problemas completos de NP.

Parece também valer para o talvez problema intermediário NP do isomorfismo de gráfico (onde podemos aplicar livremente as mesmas alterações nos dois gráficos se conhecermos o mapeamento). Gostaria de saber se isso também vale para a fatoração inteira.

Uma linguagem com apenas polinomialmente muitas instâncias sim é chamada esparsa . O teorema de Mahaney afirma que, se qualquer linguagem completa de NP for esparsa, P = NP. Como a maioria das pessoas espera que P NP, parece improvável que exista uma linguagem completa de NP com apenas polinomialmente muitas instâncias sim.$\ne$

É uma questão separada se o número de instâncias sim é exponencial. (Pode-se imaginar que o número de instâncias sim possa ser mais do que polinomial, mas menos exponencial.) A conjectura de Berman-Hartmanis é relevante aqui; implica que todos os problemas de NP-completo têm exponencialmente muitas instâncias sim. A conjectura continua sendo um problema em aberto.