RÉSOLUTION EXPONENTIALIENNE BORD LIMITE ... des preuves alternatives?

Question

Je lis le système de résolution Système de preuve exponentielle Loutte inférieure via la méthode de goulot de goulot de gettleneck de Haken pour le principe de pigeonhole, comme présenté dans l'ARORA et la complexité de calcul: une approche moderne , chapitre 15. Cependant, je ne le fais pasComme comment la preuve est présentée dans le livre et que j'ai des difficultés à la suite.

Quelqu'un peut-il connaître des sources alternatives où cette même preuve est présentée?Je sais qu'il existe différentes techniques pour montrer des limites inférieures exponentielles pour la résolution, mais je veux quelque chose basé sur le principe du pigeonhole.C'est juste que le phrasé dans ce livre est vraiment déroutant.

Answer 1

Si vous n'aimez pas la présentation d'Arora et de Barak, vous pouvez toujours jeter un coup d'œil sur le papier original de Haken.

L'approche moderne de la résolution des limites inférieures est toutefois via une largeur de résolution, comme dans un Papier classique de Ben-Sasson et Wigderson.Vous pouvez également trouver des expositions dans diverses notes de cours, par exemple par Jakob Nordström .