Etapa de redução de grau na prova de Dinur do teorema do PCP

Na etapa de redução de grau da prova de Dinur, o gráfico de entrada é transformado em um gráfico substituindo cada vértice v \ in V (G) por um conjunto de vértices, nuvem (v) , de modo que | cloud (v) | = degree_G (v) e impondo um gráfico expansor de grau d na nuvem (v) para todos os v \ in V (G) . Isso torna G ' a d + 1 gráfico regular, e a construção garante que a diferença seja reduzida apenas por um fator constante. Fiquei imaginando o que aconteceria se, em vez disso, impuséssemos um ciclo em cada nuvem? Tentei limitar a queda no espaço, mas não consegui. Então, a prova se decompõe nesta etapa?G ' v ∈ V ( L ) c l o u d ( v ) | c l o u d ( v ) | = d e g r e $G$$G'$$v \in V(G)$$cloud(v)$c l o u d ( v ) v ∈ V ( L ) L $|cloud(v)| = degree_G(v)$$cloud(v)$$v \in V(G)$$G'$

É essencial para a construção ter um expansor entre as cópias de um vértice (a "nuvem" do vértice). Caso contrário, você não poderá argumentar que o adversário que atribui valores aos vértices é melhor atribuir a esses vértices o mesmo valor.

Em particular, se em vez de um expansor você tiver um ciclo, o provador poderá atribuir um meio ciclo a um valor e o outro meio ciclo a outro valor. Dessa forma, com boa probabilidade, o verificador não capta a inconsistência entre os vértices, mas você não pode apelar para a solidez do gráfico original para provar a solidez do novo gráfico (é como permitir que o provador no gráfico original use dois atribuições diferentes para o vértice).