¿La conjetura del isomorfismo implica límites inferiores exponenciales en la densidad de testigos?

La conjetura del isomorfismo de Berman y Hartmanis establece que todos los conjuntos completos de son polinomiales en el tiempo isomorfos entre sí. Esto significa que los completos de pueden reducirse eficazmente entre sí mediante bijecciones de tiempo polinómico computables e invertibles. La conjetura implica .N P P ≠ N $NP$$NP$$P\neq NP$

La conjetura del isomorfismo implica un límite inferior exponencial en la densidad de los conjuntos completos de ya que el problema de satisfacción es denso. Me pregunto si también implica un límite inferior exponencial en la densidad de testigos para el conjunto completo de N $NP$$NP$

¿La conjetura del isomorfismo implica límites inferiores exponenciales en la densidad de testigos? ¿ Implica que los problemas completos de no pueden estar en F e w P ?$NP$$FewP$

El mejor resultado que conozco es el siguiente:

Si y N P = E X P, entonces la conjetura del isomorfismo es válida.$P=UP$$NP=EXP$

La densidad de un conjunto S se refiere al número de cadenas de longitud menor que n en el lenguaje. Un conjunto S es exponencialmente denso si su densidad es D = Ω ( 2 n ϵ ) para algunos ϵ > 0 y para infinitamente n, y disperso si D = O ( p o l y ( n ) ) .$D$$S$$n$$S$$D=\Omega(2^{n^\epsilon})$$\epsilon \gt 0$$n$$D$$O(poly(n))$

No veo cómo eso seguiría de inmediato: la conjetura del isomorfismo es sobre los idiomas, y no parece tener ninguna implicación sobre la estructura testigo de los verificadores NP. (Cada idioma tiene infinitos verificadores diferentes para él, y potencialmente podrías manipularlos para hacer cosas extrañas).

Pero su pregunta revela otra pregunta intrigante muy natural, sobre el siguiente fortalecimiento de la Conjetura del Isomorfismo:

"¿Todos los verificadores para conjuntos completos de NP son poli-temporales isomorfos?"

Es decir, queremos no solo un isomorfismo poli-tiempo entre dos idiomas NP-completos L , L ′ definidos por los verificadores V , V ′ , sino también isomorfismos ψ V , V ′ entre sus conjuntos de entrada-testigo pares que respetan el isomorfismo ϕ L , L ′ . (Nota: Hay varias formas en que uno podría definir esto formalmente). Todos N $\phi_{L,L'}$$L,L'$$V,V'$$\psi_{V,V'}$$\phi_{L,L'}$$NP$- Pruebas de dureza que puedo pensar en darle una correspondencia uno a uno de este tipo, también. Esta "Conjetura del testigo del isomorfismo" más fuerte implicaría algún tipo de respuesta afirmativa a su pregunta.

Una búsqueda rápida en Google (escribiendo 'conjetura de isomorfismo testigo') encontró una encuesta de algunos enfoques para este tipo de pregunta:

Eric Allender. Investigaciones sobre la estructura de conjuntos completos. Perspectivas en la complejidad computacional: The Somenath Biswas Anniversary Volume, Springer, 2014