Candidatos naturais à hierarquia dentro do NPI

16

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 .PNPNPINPPNPNPEu

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.NPPNPINPINPI

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,BNP
ABNPI
AB
BA

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.BA

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?NPINP

Mohammad Al-Turkistany
fonte
3
Postado aqui com base na sugestão de Kaveh depois que uma recompensa do CS Stackexchange expirou sem resposta satisfatória.
Mohammad Al-Turkistany

Respostas:

18

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.mmmm

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 ].AC0

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 .PNPPHNPNP=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) .mNP

Joshua Grochow
fonte
11
Acho a mistura silenciosa de versões de contagem e versões de decisão bastante confusa. Um anel é uma estrutura finita, e o (versão de decisão) do isomorfismo das estruturas finitas é GI-completo. Portanto, a versão de decisão do isomorfismo em anel não é mais difícil que o IG e nem mais que o fatoração inteira.
Thomas Klimpel
11
@ ThomasKlimpel: Apenas iso de estruturas finitas b / c é GI-completo não significa que, para qualquer classe específica de estruturas finitas, o problema de iso é GI-complete. Viz. O grupo iso não é conhecido nem acredita-se que esteja completo com GI. É improvável que o anel iso, quando fornecido por tabelas de adição / mult, seja GI-completo, uma vez que está em . A versão do RingIso a que me refiro na resposta acima é a dada por gens e relações. TIME(O(nlogn))
Joshua Grochow
@ThomasKlimpel: Se, por "mistura silenciosa", você estiver se referindo ao parágrafo entre parênteses, as equivalências mencionadas serão em termos de reduções de Turing no tempo polinomial (também conhecidas como reduções de Cook), e não muitas.
21414 Joshua Grochow
OK, eu li o começo da referência agora. O anel é dado por tabelas de adição / multitempo, mas estas têm uma representação compactada canônica para anéis (porque o grupo de aditivos é abeliano), portanto o resultado de completude GI para estruturas finitas não é relevante. Eu não caracterizaria essa representação como "gens e relações", porque isso soa como a "mistura silenciosa" da qual reclamei inicialmente. Observação não relacionada: eu não me referi ao parágrafo entre parênteses, nem assumi que o isomorfismo do anel deveria ser GI completo, apenas que não deveria ser mais difícil que o GI.
Thomas Klimpel
@ThomasKlimpel: Desculpe, você está certo, não é exatamente gens e relações. (E eu interpretei mal sua observação sobre GI-completo vs "não mais que GI".) Pensei ter entendido o que você queria dizer com "mistura silenciosa", mas, dado seu último comentário, não entendo mais. Mas talvez isso não seja tão relevante para cstheory.stackexchange e você pode me enviar um e-mail diretamente para ajudar a esclarecer meu entendimento (após o qual eu poderia atualizar a resposta, se necessário).
Joshua Grochow