LARGE CLIQUE IS HARD ON AVERAGE FOR RESOLUTION

摘要

We prove resolution lower bounds for k -Clique on the Erdos-Renyi random graph G ( n n ? 2 k ? 1 ) (where 1" 1 is constant). First we show for k = n c 0 , c 0 ( 0 1 3) , an exp ( ( n (1 ? ) c 0 ) ) average lower bound on resolution where is arbitrary constant. We then propose the model of a -irregular resolution. Extended from regular resolution, this model is interesting in that the power of general-over-regular resolution from all {it known} exponential separations is below it. We prove an n ( k ) average lower bound of k -Clique for this model, for {it any} k n 1 3 ? (1) .