Candidatos naturais à hierarquia dentro do NPI

22

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

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
1
Então você está procurando problemas tais que P 1 p P p P 2 com P 1N P I e P 2N P C ? PNPP1pPpP2P1NPIP2NPC
Raphael
1
Sim, mas não há redução conhecida de P para P1 (da mesma forma, nenhuma redução conhecida de P2 para P).
Mohammad Al-Turkistany
2
existem vários problemas com um estatuto semelhante ao factoring, consulte este artigo de Papadimitriou theory.stanford.edu/~megiddo/pdf/papadimX.pdf
Marcos Villagra
8
além disso, temos uma lista muito agradável em cstheory cstheory.stackexchange.com/questions/79/...
Marcos Villagra
2
por que a lista que Marcos vincula não é a resposta para sua pergunta?
Suresh

Respostas:

5

Encontrei um bom problema chamado ModularFactorial . Tome como entrada dois inteiros com quatro dígitos x e y , e a saída x !nxy . Esse problema é pelo menos tão difícil quanto oFactoringe não sabe ser difícil para oFNP. A referência é o livro recente (e bonito) de Cristopher Moore e Stephan MertensThe Nature of Computation, página 79.x!mody

Marcos Villagra
fonte
1
Acredito que o OP esteja procurando problemas no NP. Você pode reformular isso como um problema de decisão?
Zach Langley
FNP é a versão da função (ou seja, problemas de pesquisa) do NP. De fato, fatorar não está no NP, é no FNP. Por exemplo, o problema de decisão para fatoração é trivial, a complexidade é apenas O (1), mas o problema de pesquisa é a parte difícil. Como o OP deu o fatorial como exemplo, acho que essa também é uma resposta válida.
Marcos Villagra
1
A fatoração pode ser reformulada em um problema de decisão da seguinte maneira: dado um número e um número k , n contém um fator d com 1 < d k ? Existe uma versão de decisão análoga do problema ModularFactorial? nknd1<dk
Zach Langley
@ Marcos, Obrigado. Estou interessado em problemas de decisão no NP.
Mohammad Al-Turkistany
@ZachLangley, sim, é claro que concordo, mas estava pensando em outra versão de decisão, a saber, "x tem algum fator?". A resposta é apenas "sim" sempre. Você pode fazer o mesmo com o fator modular, forneça um número inteiro k e decida se é maior que k ou não. x!modyk
Marcos Villagra