Разрешение экспоненциальная нижняя граница ... Альтернативные доказательства?

Question

Я читающую разрешение доказательную систему экспоненциальной нижней оценкой через метод узкого места Haken для принципа голубя, как представлено в ароар и бараке вычислительной сложности: современный подход , глава 15. Однако я неКак и как доказательство представлено в книге, и у меня есть некоторые трудности, следующие за ним.

кто-то знает об альтернативных источниках, где представлен этот же доказательство?Я знаю, что есть разные методы, чтобы показать экспоненциальные нижние границы для разрешения, но я хочу что-то, основываясь на принципе голубя.Только что фразы в этой книге действительно запутается.

Answer 1

Если вам не нравится презентация арора и Барака, вы всегда можете взглянуть на оригинальную бумагу Haken.

Современный подход к разрешению нижних границ, однако, через ширину разрешения, как разрабатывается в Классическая статья Бен-Сассона и Вигдельсона.Вы также можете найти экспозиции в различных нотах лекции, например, путем