Descripción
Este libro aborda dos cuestiones de la Teoría de la Complejidad: el problema de la prueba de monotonicidad y la conjetura de los juegos 2 a 2.
La prueba de monotonicidad es un problema del campo de la prueba de propiedades, considerado por primera vez por Goldreich et al. en 2000. La entrada del algoritmo es una función, y el objetivo es diseñar un comprobador que realice el menor número posible de consultas a la función, acepte funciones monótonas y rechace funciones muy alejadas de ser monótonas con una probabilidad cercana a 1.
El primer resultado de este libro es un algoritmo esencialmente óptimo para este problema. El análisis del algoritmo se basa en gran medida en un análogo novedoso, dirigido y robusto de una desigualdad isoperimétrica booleana de Talagrand de 1993.
El teorema de las pruebas verificables probabilísticamente (PCP) es una de las piedras angulares de la informática teórica moderna. Un área en la que los PCP son esenciales es la de la dureza de la aproximación. En ella, el objetivo es demostrar que algunos problemas de optimización son difíciles de resolver, incluso de forma aproximada. Muchos resultados sobre la dureza de la aproximación se demostraron utilizando el teorema PCP; sin embargo, para algunos problemas no se obtuvieron resultados óptimos. Este libro aborda algunos de estos problemas, y en particular el problema de los juegos 2 a 2 y el problema de la cobertura de vértices.
El segundo resultado de este libro es una prueba de la conjetura de los juegos 2 a 2 (con completitud imperfecta), que implica nuevos resultados de dureza de la aproximación para problemas como la cobertura de vértices y el conjunto independiente. También sirve como una fuerte evidencia de la conjetura de los juegos únicos, un notorio problema abierto relacionado en la informática teórica. El núcleo de la prueba es una caracterización de pequeños conjuntos de vértices en grafos de Grassmann cuya expansión de aristas está acotada lejos de 1.
Autor: Dor Minzer
Editorial: ACM Books
Publicado: 12/06/2022
Páginas: 233
Tipo de encuadernación: Tapa blanda
Peso: 0.90lbs
Tamaño: 9.25h x 7.50w x 0.49d
ISBN13: 9781450399661
ISBN10: 1450399665
Categorías BISAC:
- Informática | Informática
- Matemáticas | Matemáticas Discretas
- Matemáticas | Análisis Matemático