Candidatos naturais à hierarquia dentro do NPI

Vamos supor que . é a classe de problemas em que não são nem nem em -Hard. Você pode encontrar uma lista de problemas conjecturados como 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 problemas, ou seja, existem problemas que são mais difíceis do que outros 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
- , - e são conjecturados como sendo , - é conhecido por reduzir a , - mas existem não conhecido reduções de para . $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 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 -Hard? $\mathsf{NPI}$ $\mathsf{NP}$

complexity-theory np-hard Mohammad Al-Turkistany
fonte

Então você está procurando problemas

tais que

com

P \in N P

$P \in \mathrm{NP}$

P_{1} \leq_{p} P \leq_{p} P_{2}

$P_1 \leq_p P \leq_p P_2$

P_{1} \in N P I

$P_1 \in \mathrm{NPI}$

P_{2} \in N P C

$P_2 \in \mathrm{NPC}$

Raphael

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

existem vários problemas com um estatuto semelhante ao factoring, consulte este artigo de Papadimitriou theory.stanford.edu/~megiddo/pdf/papadimX.pdf

Marcos Villagra

além disso, temos uma lista muito agradável em cstheory cstheory.stackexchange.com/questions/79/...

Marcos Villagra

por que a lista que Marcos vincula não é a resposta para sua pergunta?

Suresh

Respostas:

Encontrei um bom problema chamado ModularFactorial . Tome como entrada dois inteiros com quatro dígitos e , e a saída $n$ $x$ $y$ . 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! \mod y$

Marcos Villagra
fonte

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

A fatoração pode ser reformulada em um problema de decisão da seguinte maneira: dado um número

e um número

contém um fator

com

? Existe uma versão de decisão análoga do problema ModularFactorial?

n

$n$

k

$k$

n

$n$

d

$d$

1 < d \leq k

$1 < d \le k$

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

ou não.

x! \mod y

$x!\mod y$

k

$k$

Marcos Villagra