Problemas de decisión y su complejidad computacional

En teoría de la computación, un problema es un conjunto de frases de longitud finita que tienen asociadas frases resultantes también de longitud finita. Un problema de decisión es un problema en donde las respuestas posibles son «sí» o «no».

Complejidad computacional

La teoría de la complejidad computacional es la rama de la teoría de la computación que estudia, de manera teórica, la complejidad inherente a la resolución de un problema computable. Los recursos comúnmente estudiados son el tiempo (mediante una aproximación al número y tipo de pasos de ejecución de un algoritmo para resolver un problema) y el espacio (mediante una aproximación a la cantidad de memoria utilizada para resolver un problema).

TIME (f(n)) = el conjunto de lenguajes para los cuales existe una máquina de Turing determinista que los decida en tiempo que crece asintóticamente como la función f(n).

NTIME (f(n)) = el conjunto de lenguajes para los cuales existe una máquina de Turing no determinista que los decida en tiempo que crece asintóticamente como la función f(n).

Hoy en día las computadoras resuelven problemas mediante algoritmos que tienen como máximo una complejidad o coste computacional polinómico, es decir, la relación entre el tamaño del problema y su tiempo de ejecución es polinómica. Éstos son problemas agrupados en la clase P.

Los problemas que no pueden ser resueltos por nuestras computadoras (las cuales son Máquinas Determinísticas), que en general poseen costes factorial o combinatorio pero que podrían ser procesados por una máquina no-determinista, están agrupados en la clase NP. Estos problemas no tienen una solución práctica, es decir, una máquina determinística (como una computadora actual) no puede resolverlos en un tiempo razonable.

Los problemas en P son en términos generales problemas fáciles, mientras los problemas en NP pero no en P son en términos generales problemas difíciles.

La pregunta P=NP

El saber si las clases P y NP son iguales es el más importante problema abierto en Computación teórica. Incluso hay un premio de un millón de dólares para quien lo resuelva.

Sat

Problema de satisfacibilidad booleana (también llamado SAT) fue el primer problema identificado como perteneciente a la clase de complejidad NP-completo.

El SAT es el primer problema NP-completo conocido, y fue demostrado por Stephen Cooken 1971. El problema SAT se trata de un problema donde interesa saber si una expresión booleana con variables y sin cuantificadores tiene asociada una asignación de valores para sus variables que hace que la expresión sea verdadera.