Estudio de límites inferiores para la satisfacción y problemas relacionados

Título original:

A Survey of Lower Bounds for Satisfiability and Related Problems

Contenido del libro:

Podría decirse que la completitud NP constituye el concepto más generalizado de las ciencias de la computación, ya que recoge la complejidad computacional de miles de problemas importantes de todas las ramas de la ciencia y la ingeniería.

La pregunta P contra NP se refiere a si estos problemas pueden resolverse en tiempo polinómico. Hace tiempo que se conjetura una respuesta negativa, pero hasta hace poco no se conocían límites inferiores concretos en modelos generales de computación.

La satisfacción es el problema que consiste en decidir si una fórmula booleana dada tiene al menos una asignación satisfactoria. Es el primer problema que se demostró que era NP-completo, y es posiblemente el problema NP-completo más estudiado, tanto por sus propiedades teóricas como por sus aplicaciones en la práctica. A Survey of Lower Bounds for Satisfiability and Related Problems estudia los límites más bajos descubiertos recientemente para la complejidad temporal y espacial de la satisfacción y problemas estrechamente relacionados.

En él se repasan los resultados más avanzados sobre modelos generales de computación determinista, aleatoria y cuántica, y se presentan los argumentos subyacentes en un marco unificado. A Survey of Lower Bounds for Satisfiability and Related Problems es una referencia inestimable para profesores y estudiantes que investigan en teoría de la complejidad o que planean hacerlo.