Introducción a la Teoría de Computación Compleja

Descripción general:
teoría de la complejidad, en pocas palabras, una palabra de complejidad es una palabra bastante elegante, literalmente, suena compleja, pero no es un tema intimidante. Lo que realmente significa es analizar el programa o podemos decir analizar la eficiencia del programa, determinar si el programa es correcto, determinar si un programa es mejor que el otro y cómo lo hacemos exactamente de una manera muy manera cuantificada. Hay muchas variantes de este bit que generalmente estamos viendo cuando estamos haciendo cualquier programación de computadora o en general o en la mayoría de los propósitos prácticos son solo dos complejidades principales, una es la Complejidad del Tiempo y la otra es la Complejidad del Espacio (memoria ) .

La complejidad del tiempo es simple, ya que la rapidez con la que se ejecuta su código, cuánto tiempo llevará, depende de la cantidad de pasos. La complejidad del tiempo es independiente del hardware, así que supongamos que escribo un programa, y ​​podría tener una supercomputadora o una computadora portátil simple, por lo que el tiempo será diferente según el lugar donde ejecute el programa, por lo que no es una métrica muy determinista. y queremos algo muy robusto y bastante determinista, así que a continuación tenemos un paso muy simple, que no mide el tiempo real, pero sabemos que el tiempo es básicamente muy proporcional a la cantidad de pasos que toma el programa.

Ejemplo de factores de Complejidad en el Tiempo (ejecución) y el Espacio (memoria):

Ejemplo-1: más complejo

i = 1;                        1s
while( i <= 10 )              11s
{
    a = 5;                       10s
    result = i * a;              10s
    printf(“\n” /d”, result);    10s
    i++;                         10s
}

Aquí, asumimos que cada variable es igual a 2 Bytes . En el ejemplo anterior, usamos tres variables (i, a, resultado) que son 6 bytes.

Tiempo de ejecución: 52 s
Memoria (espacio): 6 bytes

Ejemplo-2: Menos complejo

a = 5;                       1s
i = 1;                           1s
while( i<=10)                  11s
{  
    result = i * a;              10s
    printf(“\n” /d”, result);    10s
    i++;                         10s 
}

Tiempo de ejecución: 43 s
Memoria (espacio): 6 bytes

Problemas en la complejidad de la computación:

• Problemas solucionables:
  se dice que un problema es solucionable primero si encuentra una solución significa que existe una solución potencial, tiene un algoritmo y un procedimiento para encontrar su solución, pero también el problema es solucionable si demostró matemáticamente que no existe una solución que significa que el problema no requiere más discusión porque sabemos que el problema nunca se puede resolver, no importa cuántas veces intentemos resolver el problema.
• Problema irresoluble:
  Los problemas irresolubles en informática son un estado temporal del problema porque un problema no tiene solución, decimos ese instante de tiempo ni somos capaces de resolver el problema ni estamos en posición de decir que el problema no se puede resolver, lo que significa en problemas irresolubles todavía estamos confusos, y la discusión sigue abierta. Y si el problema radica en este dominio, se conoce como un problema sin solución.
• Decidible Vs Indecidible :
  Básicamente, los problemas solucionables se dividen en dos categorías: Decidible e Indecidible. Antes de profundizar en el dominio de la decidibilidad, debemos tener un buen conocimiento de los algoritmos y modelos de máquinas de la Teoría de la Computación , especialmente las Máquinas de Turing .
• Problema decidible:
  cuando hablamos de los problemas decidibles, los dos términos importantes se utilizan algoritmos y procedimientos. El procedimiento es una instrucción paso a paso para resolver un problema. Un procedimiento se convierte en algoritmo cuando decimos cuál es el tiempo aproximado para resolver un problema. Cuando nos preocupamos por problemas decidibles significa que incluye tanto algoritmos como procedimientos.
• Problema indecidible:
  cuando hablamos de problemas indecidibles, no podemos predecir el tiempo del problema en el que se puede resolver un problema. Los problemas indecidibles también son solucionables y existe un procedimiento para resolver el problema, pero el problema es complejo ya que no podemos predecir el tiempo aproximado.