Математики из США и Японии решили одну из самых сложных задач в комбинаторике – вычислили девятое число Дедекинда, которое описывает количество монотонных булевых функций от девяти переменных. Это число равно 286386577668298411128469151667598498812366 и было найдено с помощью суперкомпьютера.
Числа Дедекинда – это быстрорастущая последовательность целых чисел, названная в честь немецкого математика Рихарда Дедекинда, который ввел их в 1897 году. Число Дедекинда M(n) равно количеству монотонных булевых функций от n переменных. Булева функция – это функция, которая принимает на вход n булевых переменных (то есть значений, которые могут быть либо ложными, либо истинными, или эквивалентно двоичными значениями, которые могут быть либо 0, либо 1) и выдает на выход другую булеву переменную. Она называется монотонной, если для любой комбинации входов переключение одного из входов с ложного на истинное может только вызвать переключение выхода с ложного на истинное, а не наоборот.
Вычисление чисел Дедекинда является трудной задачей, так как нет закрытой формулы для их определения, а точные значения известны только для n ≤ 9. Первые шесть чисел были получены еще в 1940 году, а седьмое и восьмое – в 1988 и 1990 годах соответственно. Девятое число оставалось неизвестным до настоящего времени.
Для его нахождения ученые использовали метод перебора всех возможных монотонных булевых функций от девяти переменных с помощью суперкомпьютера K. Этот процесс занял около 10 миллиардов часов процессорного времени и потребовал около 500 терабайт памяти. В результате было установлено, что девятое число Дедекинда равно 286386577668298411128469151667598498812366 (последовательность A000372 в базе данных OEIS).
Это открытие имеет теоретическое значение для математики, так как числа Дедекинда связаны с такими понятиями, как антицепи множеств, свободные распределительные решетки и абстрактные симплициальные комплексы. Кроме того, оно демонстрирует возможности современных вычислительных технологий для решения сложных комбинаторных задач.
Пока нет отчета об исследовании, но он должен быть представлен в сентябре на Международном семинаре по булевым функциям и их приложениям (BFA), который проходит в Норвегии.
Источник: SecurityLab