Diferencia entre revisiones de «Teoría de la complejidad computacional»
Contenido eliminado Contenido añadido
m Revertidos los cambios de 200.75.9.194 (disc.) a la última edición de MastiBot |
|||
Línea 22:
Los problemas de decisión son importantes porque casi todo problema puede ser transformado en un problema de decisión. Por ejemplo el problema ''CONTIENE-FACTORES'' descrito como: Dados dos enteros ''n'' y ''k'', decidir si ''n'' tiene algún factor menor que ''k''. Si se puede resolver ''CONTIENE-FACTORES'' con una cierta cantidad de recursos, su solución se puede utilizar para resolver ''FACTORIZAR'' con los mismos recursos, realizando una [[búsqueda binaria]] sobre ''k'' hasta encontrar el más pequeño factor de ''n'', luego se divide ese factor y se repite el proceso hasta encontrar todos los factores.
En teoría de la complejidad, generalmente se distingue entre soluciones positivas o negativas. Por ejemplo, el conjunto
Un resultado importante en teoría de la complejidad es el hecho de que independientemente de la dificultad de un problema (es decir de cuántos recursos de espacio y tiempo necesita), siempre habrá problemas más difíciles. Esto lo determina en el caso de los costes en tiempo el [[teorema de la jerarquía temporal]]. De éste se deriva también un teorema similar con respecto al espacio.
| |||