No estoy seguro si entiendo tu pregunta. Dado un algoritmo (por ejemplo, un algoritmo escrito en inglés), generalmente es posible expresarlo procesalmente en un lenguaje de programación. [ACTUALIZACIÓN: En realidad, esto no es cierto. Ha habido algoritmos teóricos expresados en términos que no pueden implementarse. Trataré de desenterrar algunos ejemplos y agregarlos aquí.]
Sin embargo, hay muchos problemas diferentes para los que no existe un algoritmo conocido y eficiente.
Uno de los más famosos es el problema de la mochila , que puede describirse como, dado un contenedor de un tamaño dado y muchos objetos diferentes de varios tamaños y formas, ¿cuál es el embalaje más eficiente del contenedor? Suena fácil, ¿verdad? Resulta que no hay soluciones conocidas (en tiempo polinómico).
- ¿Cuáles son los buenos algoritmos de similitud y métricas para textos cortos (menos de 50 palabras)?
- ¿Puede una máquina Turing aceptar una cadena de longitud 2014? ¿Por qué este problema es indecidible?
- ¿Cuál es la solución a este décimo problema polinómico de clase?
- ¿Cuál es el algoritmo de esta pregunta de Hacker-Rank?
- ¿Cuál será el algoritmo de rotación correcto en C?
Otro problema fácil de describir sin un algoritmo eficiente conocido es el problema del vendedor ambulante . Suponga que necesita conducir por la ciudad, haciendo muchas paradas diferentes en muchos lugares. ¿Cuál es la ruta más eficiente? Al igual que el problema de la mochila, todos nos encontramos con el problema del vendedor ambulante en nuestra vida cotidiana, pero resulta ser otro problema difícil para el que no existe un algoritmo conocido que siempre resuelva el problema en tiempo polinómico.
Dichos problemas se denominan “NP-completo”, lo que significa que no existe un algoritmo conocido que resuelva el problema en tiempo polinómico. Por lo general, la mejor solución para un problema de NP completo es probar todas las combinaciones posibles o algún algoritmo equivalente casi tan ineficiente.
Algunos otros ejemplos de problemas NP-completos incluyen:
Calcular grupos algebraicos de curvas elípticas
Factorizar números primos grandes
Y de wikipedia:
Problema de satisfacción booleana (sáb.)
Problema de mochila
Problema del camino hamiltoniano
Problema de vendedor ambulante
Subgrafar problema de isomorfismo
Problema de suma de subconjunto
Problema de la camarilla
Problema de cobertura de vértice
Problema conjunto independiente
Problema conjunto dominante
Problema de coloración del gráfico
