Problemas conjeturados pero no probados para ser fáciles

Tenemos muchos problemas, como la factorización, que se conjeturan fuertemente, pero no se prueban, que están fuera de P. ¿Hay alguna pregunta con la propiedad opuesta, a saber, que se conjeturan fuertemente pero no se prueba que estén dentro de P?

Hace dos décadas, una de las respuestas plausibles sería la prueba de primalidad : había algoritmos que se ejecutaban en tiempo polinómico aleatorio y algoritmos que se ejecutaban en tiempo polinomial determinista bajo una conjetura teórica de números plausibles, pero no se conocían algoritmos determinísticos de tiempo polinomial. En 2002, eso cambió con un resultado revolucionario de Agrawal, Kayal y Saxena de que la prueba de primalidad está en P. Por lo tanto, ya no podemos usar ese ejemplo.

Yo pondría pruebas de identificación polinomio como un ejemplo de un problema que tiene una buena oportunidad de estar en P, pero donde nadie ha sido capaz de demostrarlo. Sabemos de algoritmos aleatorios de tiempo polinómico para pruebas de identidad polinómica, pero no hay algoritmos deterministas. Sin embargo, hay razones plausibles para creer que los algoritmos aleatorizados pueden ser aleatorizados.

Por ejemplo, en criptografía se cree firmemente que existen generadores pseudoaleatorios altamente seguros (por ejemplo, AES-CTR es un candidato razonable). Y si eso es cierto, entonces la prueba de identidad polinómica debe estar en P. (Por ejemplo, use una semilla fija, aplique el generador pseudoaleatorio y use su salida en lugar de bits aleatorios; tomaría una gran conspiración para que esto falle. ) Esto puede hacerse formal utilizando el modelo de oráculo aleatorio; si tenemos funciones hash que pueden modelarse adecuadamente mediante el modelo de oráculo aleatorio, entonces se deduce que existe un algoritmo determinista de tiempo polinómico para la prueba de identidad polinómica.

Para una mayor elaboración de este argumento, vea también mi respuesta sobre un tema relacionado y mis comentarios sobre una pregunta relacionada .

$P=NP$

$P$

Pero, de nuevo, nadie lo sabe realmente.

$P$$P$$P$

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