Problemas conjecturados, mas não comprovadamente fáceis

Temos muitos problemas, como a fatoração, que são fortemente conjectura, mas não comprovadas, estar fora P. Há alguma pergunta com a propriedade oposto, ou seja, que eles são fortemente conjeturou, mas não provou ser dentro de P?

Duas décadas atrás, uma das respostas plausíveis seria teste de primalidade : havia algoritmos executados em tempo polinomial aleatório e algoritmos executados em tempo polinomial determinístico sob uma conjectura teórica numérica plausível, mas nenhum algoritmo de tempo polinomial determinístico conhecido. Em 2002, isso mudou com um resultado inovador de Agrawal, Kayal e Saxena de que o teste de primalidade está em P. Portanto, não podemos mais usar esse exemplo.

Eu colocaria teste de identidade polinomial como um exemplo de um problema que tem uma boa chance de estar em P, mas onde ninguém foi capaz de prová-lo. Conhecemos algoritmos aleatórios de tempo polinomial para teste de identidade polinomial, mas nenhum algoritmo determinístico. No entanto, existem razões plausíveis para acreditar que os algoritmos aleatórios podem ser des randomizados.

Por exemplo, na criptografia, acredita-se fortemente que existem geradores pseudo-aleatórios altamente seguros (por exemplo, AES-CTR é um candidato razoável). E se isso for verdade, o teste de identidade polinomial deve estar em P. (por exemplo, use uma semente fixa, aplique o gerador pseudo-aleatório e use sua saída no lugar de bits aleatórios; seria uma tremenda conspiração para que isso falhasse. ) Isso pode ser formalizado usando o modelo oracle aleatório; se tivermos funções hash que podem ser adequadamente modeladas pelo modelo aleatório do oracle, segue-se que existe um algoritmo determinístico de tempo polinomial para teste de identidade polinomial.

Para mais elaboração deste argumento, veja também minha resposta sobre um assunto relacionado e meus comentários sobre uma questão relacionada .

É uma pergunta difícil, porque não há consenso. Ainda há pessoas que conjecturar que .$P=NP$

Mas, na minha opinião, o problema mais notável com uma conjectura significativa que está em é o isomorfismo do gráfico$P$

Mas, novamente, ninguém realmente sabe.

Em geral, a "conjectura de que está em " será rara. Apenas conjeturamos que um problema está em P se ainda não tivermos um algoritmo de tempo polinomial. Mas, não conseguir encontrar um algoritmo P para ele, depois de todos esses anos, provavelmente será visto mais como "evidência" de que o problema é difícil, não fácil.$P$$P$$P$

$\sf NP\cap coNP$$e^{O(\sqrt{n})}$$n$$\sf P$