Fundamentos lógicos de la complejidad de la prueba

Opiniones de los lectores

Actualmente no hay opiniones de lectores. La calificación se basa en 2 votos.

Título original:

Logical Foundations of Proof Complexity

Contenido del libro:

Este libro trata la aritmética acotada y la complejidad de las pruebas proposicionales desde el punto de vista de la complejidad computacional.

Los primeros siete capítulos incluyen el trasfondo lógico necesario para el material y son adecuados para un curso de posgrado. A cada una de las muchas clases de complejidad se asocia una teoría de cálculo de predicados ordenada en dos partes, con inducción restringida a los conceptos de la clase, y un sistema de prueba proposicional.

El resultado es un tratamiento uniforme de muchos sistemas de la literatura, incluidas las teorías de Buss para la jerarquía polinómica y muchos sistemas dispares para clases de complejidad como AC0, AC0(m), TC0, NC1, L, NL, NC y P".