Обговорення:Сертифікат (складність обчислень)

Ця стаття є частиною Проєкту:Комп'ютерні науки (рівень: невідомий)
	Мета проєкту — створення якісних та інформативних статей на теми, пов'язані з інформатикою і комп'ютерними науками. Ви можете покращити цю статтю, відредагувавши її, а на сторінці проєкту вказано, чим ще можна допомогти. Учасники проєкту будуть вам вдячні.
???	Цю статтю ще ніхто не оцінив за шкалою оцінок статей Проєкту:Комп'ютерні науки.
	Чим допомогти:

Це сторінка обговорень та пропозицій для статті Сертифікат (складність обчислень)
Будь ласка, підписуйте свої коментарі (для цього наберіть ~~~~ або натисніть кнопку    над віконцем редагування) Нові теми починайте внизу сторінки (додати тему). Вперше у Вікіпедії? Ласкаво просимо! Часті запитання. Це сторінка для обговорення не предмета статті, а тільки цієї статті. Правила обговорень Будьте ввічливі Припускайте добрі наміри Не допускайте образ Не прискіпуйтеся до новачків

індивідуалізація

• Testing isomorphism of combinatorial and algebraic structures, by Paolo Codenotti. Chicago, Illinois, August 2011

с.38/29

2.4.2 Weisfeiler-Lehman process

One combinatorial technique we will make use of, which can be used to start a refinement process, is to assign a unique color to one of the vertices; in this case we say that we individualize that vertex (see Figure 2.4.2).

с.61/52

3.5.2 Individualization

Recall that to individualize a vertex $x\in V_{i}$ in $X$ means to assign $x$ a special color, say "red", in $X$, resulting in the structure $X_{x}$ (cf. Section 2.4.2). For each $y\in V_{i}$, let $\sigma _{y}\in G$ move $x$ to $y$. Now we have

$\mathrm {ISO} (G,X,Y)=\bigcup _{y\in V_{i}}\mathrm {ISO} (G_{x}\sigma _{y};X_{x},Y_{y})$

This recurrence thus reduces an instance of the $G$-isomorphism to $\leq n$ instances of $G_{x}$-isomorphism. To individualize a set $R$ of vertices means to individualize each $x\in R$ in succession; the cost is a factor of $\leq n^{\|R\|}$. By breaking the symmetry we hope to make sufficient progress to offset this factor.