解像度指数関数的下限...代替案は?
-
29-09-2020 - |
質問
アロラとバラックの計算複雑さに提示されたようなハーケンホール原理のためのハーケンのボトルネック法を介して解像度の証明システムの指数の上限下限を読みています:現代のアプローチ、第15章。そのプールが本にどのように提示されているかのように、そしてそれに続いていくつかの困難を持っています。
これと同じ証明が提示されている代替源を知っていますか?私は解決のために指数関数的な下限を示すためのさまざまなテクニックがあることを知っていますが、私は鳩穴の原則に基づいて何かが欲しいです。この本の中の句が本当に混乱しているということだけです。
解決
AroraとBarakの発表が好きではない場合は、いつでもハケンのオリジナルの紙を見てみることができます。
解像度の下限への現代的なアプローチは、 Classical Poper ベン - サッソンとウィグダーソンの編集。 jakob nordstrow 。
所属していません cs.stackexchange