Аноним

Цветовое кодирование: различия между версиями

Материал из WEGA
м
нет описания правки
мНет описания правки
мНет описания правки
Строка 16: Строка 16:
'''Дерандомизация'''
'''Дерандомизация'''


Полученные алгоритмы, использующие метод цветового кодирования, можно дерандомизировать с небольшой потерей эффективности. Все, что требуется для дерандомизации – это семейство раскрасок графа G = (V, E), такое, что каждому подмножеству k вершин G по крайней мере одной из этих раскрасок назначаются разные цвета. Такое семейство также называется семейством ''идеальных функций хеширования'' от {1, 2, ..., |V|} до {1, 2, ..., k}. Подобное семейство строится явным образом при помощи сочетания методов из работ [1, 9, 12, 16]. Технику дерандомизации, обеспечивающую улучшение с постоянным коэффициентом, см. в работе [5].
Полученные алгоритмы, использующие метод цветового кодирования, можно дерандомизировать с небольшой потерей эффективности. Все, что требуется для дерандомизации – это семейство раскрасок графа G = (V, E), такое, что каждому подмножеству k вершин G по крайней мере одна из этих раскрасок назначает разные цвета. Такое семейство также называется семейством ''идеальных функций хеширования'' от {1, 2, ..., |V|} до {1, 2, ..., k}. Подобное семейство строится явным образом при помощи сочетания методов из работ [1, 9, 12, 16]. Технику дерандомизации, обеспечивающую улучшение с постоянным коэффициентом, см. в работе [5].


== Основные результаты ==
== Основные результаты ==
Строка 55: Строка 55:
• Можно ли отбросить коэффициент log |V|, появляющийся в процессе дерандомизации?
• Можно ли отбросить коэффициент log |V|, появляющийся в процессе дерандомизации?


Имеют ли задача определения, содержит ли заданный граф G = (V, E) треугольник, и задача булева умножения двух матриц |V| x |V| равными по сложности?
Являются ли задача определения, содержит ли заданный граф G = (V, E) треугольник, и задача булева умножения двух матриц |V| x |V| равными по сложности?


== Экспериментальные результаты ==
== Экспериментальные результаты ==
4551

правка