4551
правка
Переименование: различия между версиями
Перейти к навигации
Перейти к поиску
→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 83: | Строка 83: | ||
'''Теорема 7. Не существует протокола переименования без ожидания для (n + 1) процессов, использующих 2n выходных имен.''' | '''Теорема 7. Не существует протокола переименования без ожидания для (n + 1) процессов, использующих 2n выходных имен.''' | ||
Доказательство. Поскольку | Доказательство. Поскольку <math>\mu_* (\sigma_* (S^{n - 1})) - 0^{n - 1} - \sum^{n}_{i = 0} (-1)^i \alpha (face_i(S^{n - 1}))</math> является циклом, из теоремы 5 следует, что она гомологична <math>k \cdot \partial 0^n</math> для некоторого целого числа k. Поскольку <math>\mu</math> симметрична на границе <math>\sigma(S^n)</math>, знакопеременная сумма по (n – 1)-мерным граням <math>S^n</math> дает: | ||
является циклом, из теоремы 5 следует, что она гомологична k | |||
<math>\mu_* (\partial \sigma_* (S^n)) - \partial 0^n \sim (n + 1) k \cdot \partial 0^n</math> | |||
или | |||
<math>\mu_* (\partial \sigma_* (S^n)) \sim (1 + (n + 1) k) \cdot \partial 0^n</math>. | |||
Поскольку не существует значения k, для которого (1 + (n+1)k) равно нулю, цикл | Поскольку не существует значения k, для которого (1 + (n + 1)k) равно нулю, цикл <math>\mu_* (\partial \sigma_* (S^n))</math> не является границей, что противоречит предположению. □ | ||
□ | |||
== Применение == | == Применение == | ||