Es la parte de la teoría de la computación que estudia los recursos requeridos durante el calculo para resolver un problema los cuales se dividen en: el tiempo y el espacio.
Los problemas de decisión se clasifican en conjuntos de complejidad llamadas clases de complejidad:
Clase de complejidad P
Es el conjunto de los problemas de decisión que puedan ser resueltos en tiempo polinómico calculado a partir de la entrada por una maquina de turins determinista y que corresponde a problemas que pueden ser resueltos aun en el peor de sus casos.
Ejemplo:
1.
Saber si un numero entero es primo.
2.
Saber si una frase pertenece a un conjunto de frases.
Clase de complejidad NP
Es el conjunto de los problemas de decisión que pueden ser resueltos por una maquina de turins no determinista en tiempo polinómico las cuales tienen la propiedad de que su solución puede ser verificada.
Clase de complejidad NP-Completo
Es el subconjunto de los problemas de decisión en NP que destacan por su extrema complejidad y que decimos se hayan en la frontera externa de la clase NP.
2 comentarios:
okok, ya ando checando esto O.O
ammm... si el ultimo va a ser tuyo tuyo de ti, ammm.. ponle un fondo de planilla diferente a los demas para ke se resalte
y pss si hay como muchos fondos, pss ponle uno diferente a cada uno =P
saludines ^^
Woo! buen aporte , bien explicado facil de comprender :D
Publicar un comentario