Теоретико-групповые и теоретико-числовые вычисления
В работе [BK] приведены чекеры для решения некоторых теоретико-групповых и теоретико-числовых проблем, некоторые из которых приведены ниже.
Проблема эквивалентного поиска.
Пусть S – множество и G – группа, групповые действия в которой, осуществляются над элементами множестваS. Для a,bÎS элемент aºGb, тогда и только тогда, когда g(a)=b для некоторого g из G. Проблема эквивалентного поиска заключается в нахождении g
такого, что g(a)=b, если aºGb для a и b, принадлежащих множеству S. Если существует эффективный вероятностный алгоритм поиска gÎG, тогда существует [BK] эффективный программный чекер для данной проблемы. Примеров решения задач эффективного эквивалентного поиска достаточно много. К ним относятся проблема поиска изоморфизма графов (см. дальше), решение задачи квадратных вычетов, обобщенная проблема дискретных логарифмов, задачи подобные «Кубику Рубика», ряд задач из теории кодирования и др. [BK].
Проблема пересечения групп.
Пусть G и H – группы перестановок, определенные некоторыми генераторами групп. Генераторы представляются как перестановки над [1,...,n]. Проблема пересечения групп заключается в нахождении генераторов для GÇH. В работе показывается [BK], что можно построить программный чекер для данной проблемы.
Проблема расширенного нахождения НОД.
Проблема расширенного нахождения наибольшего общего делителя (которая отличается от нахождения НОД посредством алгоритма Евклида) заключается в нахождении для двух положительных целых a и b
целого d=НОД(a,b) и целых u и v таких, что au+bv=d.
Чекер для решения расширенного нахождения НОД по входу двух положительных целых a и b, целого d и целых u и v
выдать «Сбой», если d не делит a или d
не делит b или au+bv¹d. В противном случае выдать «Норма». Эффективность и корректность данного чекера легко доказывается.
