해상도 기하 급수적 인 하한 ... 대체 증거?

문제

ARORA 및 BARAK의 전산 복잡성 : 현대적인 접근 , 제 15 장, 제 15 장, 제 15 장, 나는그 증거가 책에 어떻게 제시되는지처럼 나는 그것을 따라 어려움을 겪고 있습니다.

이 동일한 증거가 제시되는 대체 소스를 알고 있습니까?해상도의 지수적 인 낮은 경계를 보여주는 다른 기술이 있지만 비둘기 구멍 원리에 따라 무언가를 원한다는 것을 알고 있습니다.이 책의 표현이 진정으로 혼란스러워지는 것입니다.

해결책

아로라와 바락의 프리젠 테이션을 좋아하지 않는다면 언제나 Haken의 원래의 종이를 살펴볼 수 있습니다.

해상도 하한에 대한 현대적인 접근법은 벤 - sasson 및 wigderson의 클래식 종이 .예를 들어 Jakob Nordström .

라이센스 : CC-BY-SA ~와 함께 속성

제휴하지 않습니다 cs.stackexchange