Risoluzione esponenziale limite inferiore ... Prove alternative?

Question

Sto leggendo il sistema a prova di risoluzione del sistema più basso per il metodo del collo di bottiglia di Haken per il principio di Pigeonhole come presentato in Arora e Barak complessità computazionale: un approccio moderno , capitolo 15. Tuttavia, non lo faccioCome la prova è presentata nel libro e sto avendo delle difficoltà a seguirlo.

Qualcuno conosce fonti alternative in cui viene presentata questa stessa prova?So che ci sono diverse tecniche per mostrare limiti ridotti esponenziali per la risoluzione, ma voglio qualcosa in base al principio di Pigeonhole.È solo che il fraseggio in questo libro è davvero confuso.

Answer 1

Se non ti piace la presentazione di Arora e Barak, puoi sempre dare un'occhiata alla carta originale di Hakken.

L'approccio moderno alle limiti inferiori della risoluzione è, tuttavia, tramite la larghezza della risoluzione, come elaborato in un carta classica di Ben-Sasson e Wigderson.Puoi anche trovare esposizioni in varie note di lezione, ad esempio da jakob nordström .