для Bcex'/^l^^.w^^^ft . Если i;T=T , то ^ называется морфизмом гиперграфа Т , и группу всех автоморфизмов ^ обозначим через OiUtT,

Алгорифлическая постановка задачи об изоморфизме состоит в оценке сложности задачи распознавания: изоморфны ли два данных графа или нет (см.напр.[l]). Эта задача считается трудной ( вольно подробная библиография по попыткам ее решения приведена в [з]) - остается невыясненным вопрос, принадлежит ли она классу задач, распознаваемых в полиномиальное время или нет.

При первом сведении задачи об изоморфизме (к,Kl) - фов строится полная система из Г1 +1 инвариантного полинома. Причем jfl из них имеют простой вид и значения их могут быть быстро вычислены, оставшийся же (Г1 +0 -ый полином с помощью известных схем вычисления вычисляется долго (к тому же не видно эффективного способа его задания). Если бы удалось предъявить вычисление значений этого полинома в полиномиальное время, то принадлежность изоморфизма графов классу задач, распознаваемых в полиномиальное время, была бы установлена.

I . Обозначим через Fa примитивное поле характеристики й ( Л - простое или нуль). Назовем полином P(<X[^...î>) от ïl ременных с коэффициентами из поля га инвариантным Cl - номом или просто инвариантом для Gr^ j^ » ^^^^ для любого Т€ GfK^n и любой перестановки %€$п выполнено ство Р(<Т^^...^^>)= P№(t^).,,^a^)>). Система (конечная или бесконечвая) инвариантов {p^j называется полной, если для любых Т,Т€ Ст^^^ , из того, что P;^(<Tt^...iK^)=Pj(<Ti|...tx>) для всех j , следует, что Т'^Т . Обозначим через Я = /1(0г,1с,а) кольцо инвариантных й -полиномов для CrK^rt; ^^рез f (а,к,п) • его поле "частных.

Приведем примеры наиболее простых инвариантов. Пусть МсСг|^^ и элементами M являются нули и единицы (это чение используем и ниже). Положим

где произведение берется по всем Х|,^..4к » ^'^ которых Ivlj^^^.j^^si. Тогда Pu = ZI h г..s ^ инвариант.

ТЕОРЕМА I. Для всяких й^к^П существует полная ма инвариантов для Сгк ri » содержащая fl ^^ элемент, дый из которых является Fa -линейной комбинацией тов (Ри].

57