Acabamos de aprender sobre a auto-redutibilidade nas aulas. Meu professor e nosso livro não se comprometeram a dizer que todos os problemas em PN são auto-redutíveis, mas não parecia haver exemplos de problemas que não sejam. Fiquei me perguntando se existem exemplos, ou se é apenas uma situação em que você não pode provar um negativo facilmente. Wikipedia diz apenasIt is conjectured that the integer factorization problem is not self-reducible.
O Google encontrou um resultado , que parece afirmar que a coloração do gráfico planar 4 não é auto-redutível porque a coloração LF-k para um gráfico planar se reduz a essa redução, mas eu não conseguia seguir a prova no momento.
Este é um exemplo real de uma reprovação de auto-redutibilidade, e existem outros?
fonte
Respostas:
De fato, o artigo mostra que a coloração do gráfico planar quatro não é auto-redutível no sentido de Schnorr. Existem vários outros sentidos, em alguns dos quais todo problema em P é auto-redutível. Veja o documento de acompanhamento de Große, Rothe e Wechsung . Não tenho conhecimento de nenhum outro resultado desse tipo. Examinando todos os trabalhos que citam o trabalho mencionado (isso pode ser feito usando o Google Scholar, por exemplo), nenhum apresenta problemas desse tipo.
fonte