No hay mucha evidencia, pero hay piezas de información “sugestivas” que, si se inclinara de esa manera, podrían leerse como soporte de P = NP.
(1) Se pensó que muchos problemas no estaban en P, pero a alguien se le ocurrió una solución lo suficientemente inteligente. Vea ¿Qué problemas alguna vez se pensó que no podían resolverse en el tiempo polinómico, pero que finalmente lo fueron?
(2) P es muy, muy grande y acabamos de raspar su superficie. Elija su número finito grande favorito B (un googolplex, un número de Graham, un ÁRBOL (3), lo que sea). Nadie sabe realmente de qué es capaz un algoritmo [matemático] \ Theta (n ^ {B}) [/ matemático] porque nos falta cualquier manera significativa de interactuar con tales monstruos. Por lo tanto, se cree que en algún lugar de este enorme bosque inexplorado y misterioso no hay algo adecuado para convertir NP a P.
- ¿Cuáles son algunos de los temas de teoría de gráficos que necesito aprender para hacer el bien en la programación competitiva?
- Cómo resolver este problema matemático discreto
- Si hubiera un algoritmo de tiempo polinómico para algo como 3SAT, ¿qué tan probable es que sea algo elegante y / o simple?
- ¿Cuáles son algunos temas imprescindibles en matemáticas discretas y probabilidad de programación competitiva?
- ¿Cuál es el papel de las matemáticas en la programación de computadoras?
Ver ¿Por qué Donald Knuth piensa que P = NP? donde se menciona el teorema de Robertson-Seymour. Este teorema dice que hay un algoritmo de tiempo polinómico para reconocer gráficos menores, ¡pero no es constructivo y no sabemos cómo construirlo para muchos de los gráficos posibles! Y eso también es solo un algoritmo de tiempo cuadrático.
(3) A pesar de nuestros mejores esfuerzos, realmente no hemos avanzado mucho demostrando lo contrario. De hecho, algunos de nuestros mejores resultados son que ciertas clases de técnicas de prueba simplemente no están a la altura. Consulte ¿Qué es una explicación intuitiva de las barreras de prueba natural, relativización y algebrización para resolver el problema [matemático] P [/ matemático] versus [matemático] NP [/ matemático]? o mejor aún, el artículo de Scott Aaronson sobre algebrización (que cubre los otros dos resultados de forma resumida): http://www.scottaaronson.com/pap…
Pero incluso esa meta-prueba comprende cuán lejos estamos del progreso significativo que separa las dos clases. Una entrada de blog de Ken Regan (Carta perdida de Godel: DC Post) señala nuestra profunda ignorancia de los límites inferiores:
- No se conoce un límite inferior de tiempo superlineal para ninguno de los problemas NP completos como SAT que en realidad están en tiempo lineal no determinista, si se permite que las máquinas de Turing tengan cintas planas.
- No se conoce el límite inferior del tamaño del circuito superlineal para ninguna función en [math] E ^ {NP} [/ math], aunque [math] E = DTIME [2 ^ {O (n)}] [/ math] es una clase de tiempo uniforme intratable y las consultas de oráculo pueden ser exponencialmente largas.
- De hecho, el límite inferior del tamaño de circuito más alto conocido para tal “función explícita” es [matemática] 5n-o (n) [/ matemática], e incluso ese límite “engaña” al excluir XOR y su negación de la base de la puerta; Además, la técnica para ello no puede ir más allá.
- La técnica principal para los límites inferiores del tamaño del circuito algebraico supera el tamaño [math] \ Theta (n \ log n) [/ math].
- Incluso el famoso [matemático] \ Omega (n \ log n) [/ matemático] límite inferior para la clasificación, que se enseña en estructuras de datos de pregrado y cursos de algoritmos, es falso en modelos razonables.
(¡Quizás algunos de estos han cambiado en los últimos 3 años!) Podríamos concluir, con Mauricio Karchmer, que “No podemos probar límites inferiores porque son falsos, y no podemos probar límites superiores porque somos estúpidos. ”
