108
правок
Изменения
Нет описания правки
|statement = '''Graph Nonisomorphism(GNI)''' <tex>\in \mathrm{PCP}[poly(n), O(1)]</tex>
|proof =
Даны графы на <tex>n</tex> вершинах <tex>G_1</tex> и <tex>G_2</tex>. Требуется проверить, изоморфны ли они друг другу. <br/>Сперва пронумеруем все возможные графы на <tex>n</tex> вершинах. Не умаляя общности, будем считать, что <tex>\pi</tex> над троичным алфавитом. <br/>Будем считать корректной <tex>\pi</tex>:<br/>* <tex>\pi[k] = 0</tex> тогда и только тогда, когда граф номер <tex>k</tex> изоморфен <tex>G_1</tex> и <tex>G_2</tex>;* <tex>\pi[k] = 1</tex> тогда и только тогда, когда граф номер <tex>k</tex> изоморфен <tex>G_1</tex> и неизоморфен <tex>G_2</tex>;* <tex>\pi[k] = 2</tex> тогда и только тогда, когда граф номер <tex>k</tex> неизоморфен <tex>G_1</tex> и изоморфен <tex>G_2</tex>.Верификатором <tex>V</tex> будет вероятностная МТ, работающая эквивалентно следующему псевдокоду:<br/> p(<tex>\langle G_1, G_2 \rangle</tex>) { i = random{1, 2}; <tex>\phi</tex> = random permutation{1..n}; <tex>H</tex> = <tex>\phi(G_i)</tex>; return <tex>\pi[\#H] == i</tex>; }Проверим полноту и обоснованность:* '''Полнота''': если графы неизоморфны, то существует <tex>\pi</tex> такая, что всякий её символ равен 1 или 2 и задан корректно. Тогда на этой <tex>\pi</tex> верификатор всегда вернёт 1.* '''Обоснованность''': если графы изоморфны, то благодаря случайному выбору <tex>i</tex> вероятность ошибки не превышает <tex>{}^1/{}^2</tex>.
}}
