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 .P≠NPP≠NPNPINPINPNPPPNPNPNPINPI
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.NP≠PNP≠PNPINPINPINPINPINPI
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∈NPA,B∈NP
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.BBAA
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?NPINPINPNP
Então você está procurando problemas tais que P 1 ≤ p P ≤ p P 2 com P 1 ∈ N P I e P 2 ∈ N P C ? P∈NPP∈NPP1≤pP≤pP2P1≤pP≤pP2P1∈NPIP1∈NPIP2∈NPCP2∈NPC
Sim, mas não há redução conhecida de P para P1 (da mesma forma, nenhuma redução conhecida de P2 para P).
existem vários problemas com um estatuto semelhante ao factoring, consulte este artigo de Papadimitriou theory.stanford.edu/~megiddo/pdf/papadimX.pdf
além disso, temos uma lista muito agradável em cstheory cstheory.stackexchange.com/questions/79/...
por que a lista que Marcos vincula não é a resposta para sua pergunta?
Encontrei um bom problema chamado ModularFactorial . Tome como entrada dois inteiros com quatro dígitos x e y , e a saída x !nnxxyy . 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!modyx!mody
Acredito que o OP esteja procurando problemas no NP. Você pode reformular isso como um problema de decisão?
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.
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? nnkknndd1<d≤k1<d≤k
@ Marcos, Obrigado. Estou interessado em problemas de decisão no NP.
@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!modyx!modykk