Том 1, номер 2, 1994 г., Стр. 40-60
УДК 519.147
А. Д. Коршунов
О сложности покрытий числовых множеств арифметическими прогрессиями
Аннотация:
Предложен алгоритм покрытия произвольных множеств из множества первых $n$ натуральных чисел арифметическими прогрессиями. Показано, что сложность получаемого покрытия любого случайного подмножества по порядку равна сложности минимального покрытия.
Библиогр. 7.
Коршунов А. Д. 1
1. Институт математики им. С. Л. Соболева СО РАН,
пр. Акад. Коптюга, 4, 630090 Новосибирск, Россия
Статья поступила 29 марта 1994 г.
