La cuestión de la complejidad real de los problemas completos de NP. Se sospecha que solo se puede obtener una solución perfecta en tiempo factorial. El conjunto de problemas NP completos incluye el problema del vendedor ambulante (ruta más corta a través de N destinos en un mapa) y el problema de la mochila: dada la mochila N de diferentes tamaños y M objetos de diferentes tamaños donde el tamaño total de todas las mochilas es el mismo como el tamaño total de todos los objetos: acomode todos los objetos en las mochilas. Por supuesto, hay más problemas en el conjunto. Si se puede demostrar que cualquiera de los problemas de NP Complete tiene una complejidad particular, entonces todos los problemas de NP Complete tienen esa complejidad.
Otro problema es la prueba de la corrección de un programa. Para cualquier otra cosa que no sean los programas más triviales, la prueba de corrección es tan compleja que es complejo de muchos órdenes de magnitud demostrar la corrección de lo que era escribir el programa en primer lugar. Es tan complejo que es más un error proNE que escribir el software en primer lugar. Por lo tanto, probamos los programas como un cuadro negro en lugar de probar la corrección basada solo en la fuente
- Cómo arreglar el wifi de mi computadora portátil cuando su controlador no se actualiza
- ¿Cuáles son las características más importantes de WAN?
- Cómo asignar la dirección IP correcta basada en la dirección de subred y la máscara
- ¿Cómo configuro un enrutador Cisco 1841 desde cero?
- Cómo construir mi propia VPN
