Предположим, что и G 2 являются двумя неориентированными графами на множестве вершин { 1 , … , n } . Графы изоморфны тогда и только тогда, когда существует перестановка Π такая, что G 1 = Π ( G 2 ) , или более формально, если существует перестановка Π такая, что ( i , j ) является ребром в G 1 тогда и только тогда если ( Π ( i ) , Π ( j это ребро в G 2 . Проблема изоморфизма графов - это проблема определения изоморфности двух данных графов.
Есть ли операция над графами, которая производит «усиление зазора» в стиле доказательства Динура теоремы PCP ? Другими словами, существует ли вычисляемое преобразование за полиномиальное время из в ( G ′ 1 , G ′ 2 ) такое, что
- если и G 2 изоморфны, то G ' 1 и G ' 2 также изоморфны, и
- если и G - не изоморфны, то для каждой перестановки П , граф G ' 1 является « ε -far» от П ( G ' 2 ) для некоторых малых постоянная е , где & epsi ; -far означает , что , если мы выбираем ( i , j ) равномерно случайным образом, то с вероятностью ϵ либо
- является ребром G ′ 1 и ( Π ( i ) , Π ( j ) ) не является ребром G ′ 2 , или
- не является ребром в G ′ 1, а ( Π ( i ) , Π ( j ) ) является ребром в G ′ 2 .
cc.complexity-theory
graph-isomorphism
pcp
Андре Шайо
источник
источник
Ответы:
Я не знаю, могла ли такая вещь существовать или нет. Но интересно (и, возможно, своевременно) отметить, что такое «усиление щели», вероятно, подразумевает квазиполиномиальный алгоритм времени для изоморфизма графов (отличный от недавно анонсированного)
В этой статье дается алгоритм аппроксимации для задачи «MAX-PGI» максимизации согласованных пар ребер / не ребер; если мы уменьшаем GI до «Gap-MAX-PGI», то мы можем приблизиться, чтобы различить, на какой стороне разрыва мы находимся.
Итак, я думаю, что доказательство Динуром теоремы PCP вряд ли будет непосредственно обобщено на такой «усилитель с зазором», учитывая препятствия, которые должны быть преодолены.
источник