108
правок
Изменения
Нет описания правки
Сперва пронумеруем все возможные графы на <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/>
