Книга Ароры и Барака содержит примечания к главе о PCP.
Мы отмечаем, что общая стратегия Динура в некоторой степени напоминает зигзагообразную конструкцию графов расширителей и детерминистический алгоритм логарифмического пространства Рейнгольда для ненаправленной связи, описанный в главе 20, что предполагает, что между этими различными областями исследований ожидается установление большего количества связей. (стр. 494)
Что именно подразумевается под этим воспоминанием? Есть ли общее свойство / лемма, которые можно «вычеркнуть» из этих двух доказательств?
cc.complexity-theory
pcp
sdcvvc
источник
источник
Ответы:
Точный ответ на ваш вопрос дает Одед Голдрайх в своей статье «Смело, умеренно: общая тема в четырех последних работах».
Вот ссылка: http://www.wisdom.weizmann.ac.il/~oded/COL/brave.pdf
источник