Candidatos naturais à hierarquia dentro do NPI

Vamos supor que . N P I é a classe de problemas em N P que não são nem P nem em N P -Hard. Você pode encontrar uma lista de problemas conjecturados como N P I aqui .$\mathsf{P} \neq \mathsf{NP}$$\mathsf{NPI}$$\mathsf{NP}$$\mathsf{P}$$\mathsf{NP}$$\mathsf{NPI}$

Teorema de Ladner nos diz que se , então não há uma hierarquia infinita de N P I problemas, ou seja, existem N P I problemas que são mais difíceis do que outros N P I problemas.$\mathsf{NP}\neq\mathsf{P}$$\mathsf{NPI}$$\mathsf{NPI}$$\mathsf{NPI}$

Estou procurando candidatos para esses problemas, ou seja, estou interessado em pares de problemas
- , - A e B são conjecturados como sendo N P I , - A é conhecido por reduzir a B , - mas existem não conhecido reduções de B para a .$A,B \in \mathsf{NP}$
$A$$B$$\mathsf{NPI}$
$A$$B$
$B$$A$

Ainda melhor se houver argumentos para apoiá-los, por exemplo, existem resultados que não se reduz a A assumindo algumas conjecturas na teoria da complexidade ou criptografia.$B$$A$

Existem exemplos naturais de tais problemas?

Exemplo: O problema de isomorfismo do gráfico e o fator de fatoração de número inteiro estão conjecturados em e há argumentos que apóiam essas conjecturas. Existem quaisquer problemas de decisão mais difícil do que esses dois, mas não se sabe serem N P -Hard?$\mathsf{NPI}$$\mathsf{NP}$

Grupo Isomorfismo Gráfico Isomorfismo ≤ m Isomorfismo em anel. Também fatoração inteira ≤ m isomorfismo do anel [ Kayal e Saxena ]. Também Graph Automorphism ≤ m Graph Isomorphism.$\leq_m$$\leq_m$$\leq_m$$\leq_m$

Não apenas não existem reduções conhecidas de outra maneira, como também não há redução de do Graph Iso para o Group Iso [ Chattopadhyay, Toran e Wagner ].$\mathsf{AC}^0$

Observe que uma redução do isomorfismo do anel para o isomorfismo gráfico também forneceria uma redução do fatoramento inteiro para o isomorfismo gráfico. Para mim, essa redução seria surpreendente, embora talvez não seja chocante.

(Para Graph Automorphism vs Graph Isomorphism, suas versões de contagem são conhecidas por serem equivalentes entre si e equivalentes a decidir o Graph Isomorphism. No entanto, isso não significa necessariamente muito, pois a versão de contagem da correspondência bipartida é equivalente à versão de contagem do SAT. )

Eu não acho que exista um consenso real sobre qual deles, se houver algum, está realmente . Se qualquer um destes problemas é N P -completo então P H entra em colapso para o segundo nível. Se factoring é N P -completo, então ele cai para o primeiro nível, ou seja N P = C O N P .$\mathsf{P}$$\mathsf{NP}$$\mathsf{PH}$$\mathsf{NP}$$\mathsf{NP} = \mathsf{coNP}$

Além disso, pareço lembrar que o uso de técnicas semelhantes à Ladner pode mostrar que qualquer ordenação parcial contável pode ser incorporada na ordenação dos problemas em N P (portanto, não é apenas uma hierarquia, mas uma ordem parcial contável arbitrariamente complicada) .$\leq_{m}$$\mathsf{NP}$