Resolución exponencial Bound Bound ... Pruebas alternativas?

Question

Estoy leyendo el sistema de prueba de prueba de resolución unido exponencial a través del método de cuello de botella de Haken para el principio de Pickeehole como se presenta en la complejidad computacional de Arora y Barak: un enfoque moderno , Capítulo 15. Sin embargo, noMe gusta cómo se presenta la prueba en el libro y estoy teniendo algunas dificultades después de eso.

¿Alguien sabe de fuentes alternativas donde se presenta esta misma prueba?Sé que hay diferentes técnicas para mostrar los límites más bajos exponenciales para la resolución, pero quiero algo basado en el principio de palo.Es solo que los frases en este libro son verdaderamente confusos.

Answer 1

Si no te gusta la presentación de Arora y Barak, siempre puedes echar un vistazo al papel original de Haken.

El enfoque moderno para la resolución Los límites más bajos se encuentra a través del ancho de la resolución, como se elaboró en una papel clásico de Ben-Sasson y Wigderson.También puede encontrar exposiciones en varias notas de conferencia, por ejemplo, por jakob nordström .