108
правок
Изменения
Нет описания правки
|statement = '''Graph Nonisomorphism(GNI)''' <tex>\in \mathrm{PCP}[poly(n), O(1)]</tex>.
|proof =
<tex>G_1</tex> и <tex>G_2</tex> {{---}} графы на <tex>n</tex> вершинах. Требуется проверить, изоморфны неизоморфны ли они друг другу. <br/>
Сперва пронумеруем все возможные графы на <tex>n</tex> вершинах. Не умаляя общности, будем считать, что <tex>\pi</tex> над троичным алфавитом. <br/>
Будем считать корректной <tex>\pi</tex>:<br/>
