Candidatos naturales para la jerarquía dentro de NPI

Supongamos que . N P I es la clase de problemas en que no están ni en ni en N P -hard. Puede encontrar una lista de problemas conjeturados como N P I aquí .$\mathsf{P} \neq \mathsf{NP}$$\mathsf{NPI}$$\mathsf{NP}$$\mathsf{P}$$\mathsf{NP}$$\mathsf{NPI}$

El teorema de Ladner nos dice que si entonces hay una jerarquía infinita de problemas N P I , es decir, hay problemas N P I que son más difíciles que otros problemas N P $\mathsf{NP}\neq\mathsf{P}$$\mathsf{NPI}$$\mathsf{NPI}$$\mathsf{NPI}$

Estoy buscando candidatos para tales problemas, es decir, estoy interesado en pares de problemas
- , - Se conjetura que A y B son N P I , - Se sabe que A se reduce a B , - pero hay sin reducciones a partir conocida B a a .$A,B \in \mathsf{NP}$
$A$$B$$\mathsf{NPI}$
$A$$B$
$B$$A$

Aún mejor si hay argumentos para apoyarlos, por ejemplo, hay resultados que no reduce a A suponiendo algunas conjeturas en la teoría de la complejidad o la criptografía.$B$$A$

¿Hay ejemplos naturales de tales problemas?

Ejemplo: Se supone que el problema de isomorfismo gráfico y el problema de factorización de enteros están en y hay argumentos que respaldan estas conjeturas. ¿Hay algún problema de decisión más difícil que estos dos pero no se sabe que es N P- duro?$\mathsf{NPI}$$\mathsf{NP}$

Isomorfismo grupal Isomorfismo gráfico ≤ m Isomorfismo en anillo. También Factorización entera ≤ m Isomorfismo de anillo [ Kayal y Saxena ]. También Graph Automorphism ≤ m Graph Isomorphism.$\leq_m$$\leq_m$$\leq_m$$\leq_m$

No solo no hay reducciones conocidas a la inversa, sino que probablemente no hay reducción de de Iso de gráfico a Iso de grupo [ Chattopadhyay, Toran y Wagner ].$\mathsf{AC}^0$

Tenga en cuenta que una reducción de isomorfismo en anillo a isomorfismo gráfico también proporcionaría una reducción de factorización de enteros a isomorfismo gráfico. Para mí, tal reducción sería sorprendente, aunque quizás no impactante.

(Para Graph Automorphism vs Graph Isomorphism, se sabe que sus versiones de conteo son equivalentes entre sí y equivalentes a decidir Graph Isomorphism. Sin embargo, eso no necesariamente dice mucho, ya que la versión de conteo de coincidencia bipartita es equivalente a la versión de conteo de SAT. )

Creo que no hay un consenso real en cuanto a que, en su caso, de estos son en realidad en . Si alguno de estos problemas es N P -completo, entonces P H colapsa al segundo nivel. Si la factorización es N P -Complete, entonces se colapsa para el primer nivel, es decir, N P = c o N P .$\mathsf{P}$$\mathsf{NP}$$\mathsf{PH}$$\mathsf{NP}$$\mathsf{NP} = \mathsf{coNP}$

Además, me parece recordar que el uso de técnicas similares a Ladner puede mostrar que cualquier orden parcial contable puede integrarse en el orden de los problemas en N P (por lo que no es solo una jerarquía, sino un orden parcial contable arbitrariamente complicado) .$\leq_{m}$$\mathsf{NP}$