Resolução Exponencial Bruta inferior ... Provas alternativas?

Question

Eu estou lendo o sistema à prova de resolução Aplicada inferior exponencial via Método de gargalo de Haken para o princípio de pombo, conforme apresentado na complexidade computacional de Arora e Barak: uma abordagem moderna , capítulo 15. No entanto, nãocomo como a prova é apresentada no livro e estou tendo algumas dificuldades seguindo isso.

Alguém sabe de fontes alternativas onde essa mesma prova é apresentada?Eu sei que existem diferentes técnicas para mostrar limites inferiores exponenciais para resolução, mas quero algo com base no princípio da pomba.É só que o fraseado neste livro é verdadeiramente confuso.

Answer 1

Se você não gosta da apresentação de Arora e Barak, você sempre pode dar uma olhada no papel original de Haken.

A abordagem moderna para a resolução de limites inferiores é, no entanto, via largura de resolução, como funcionou em um papel clássico de Ben-Sasson e Wigderson.Você também pode encontrar exposições em várias notas de palestras, por exemplo, por jakob nordström .