Ценность формулировки и доказательств NP-полноты теоретико-числовых задач связана с тем, что для таких задач в настоящее время отсутствуют (и, скорее всего, будут отсутствовать в будущем) полиномиальные по времени (числу шагов на машине Тьюринга) решающие их алгоритмы.
На первый взгляд, простейшей и наиболее часто решаемой задачей математики является задача решения линейных диофантовых уравнений, сравнений и различного вида неравенств. Однако постоянно исследуются всё новые и новые методы их решения (см., например, [1]).
Для компьютерной реализации алгоритма (предиката) важно, чтобы он принадлежал классу FP (соответственно классу P). Кроме того, для многих задач полезно знать, что задача является NP-трудной (NP-полной), поскольку это условие в настоящее время не позволяет эффективно реализовать её на компьютере.
Целью настоящей работы является выявление простейших NP-полных задач, связанных с разрешимостью систем линейных диофантовых дизсравнений.
Эта цель в некоторой степени дополнительна к цели, поставленной в [2], где выявляются классы графов, в результате сужения на которые NP-трудные задачи имеют полиномиально эффективное решение, и к цели, поставленной в [3] и более тесно связанной с вычислительной сложностью алгоритмов решения систем сравнений специального вида.
Для математиков одними из наиболее простых объектов, часто возникающих в исследованиях, являются системы линейных диофантовых уравнений и сравнений. В обширном списке NP-полных задач, приведённом в [4], есть всего одна задача, относящаяся к рассматриваемым объектам. Эта задача названа переводчиком система несравнимостей (результат получен в [5]). К сожалению, в её формулировку на русском языке вкралась опечатка: вместо знака = должен быть знак =. Приведём формулировку задачи без опечатки.
Система несравнимостей (в [4] под аббревиатурой АТЧ2)
УСЛОВИЕ. Задан набор {(a1, b-1),..., (an, bn)} упорядоченных пар положительных целых чисел таких, что ai < bi при 1 < i < n.
ВОПРОС. Существует ли такое целое число х, что х ^ ai(mod bi), 1 < i < n?
Рассмотрим частный случай этой задачи при bi = • • • = bn = m и попарно различных a1,..., an, которую будем называть Система несравнимостей по единому модулю. В названии этой задачи полезно было бы отметить, что каждая несравнимость линейна и содержит только одну переменную с коэффициентом при ней, равным 1. Однако сохранена терминология из [4].
Новая задача может быть решена конечным перебором, но при этом алгоритм будет требовать экспоненциального числа шагов от длины исходных данных. Предложим для её решения полиномиальный алгоритм.
Для получения полиномиального по времени алгоритма решения задачи Система несравнимостей по единому модулю сформулируем утверждение.
Утверждение 1. Задача Система несравнимостей по единому модулю имеет положительное решение тогда и только тогда, когда n < m.
Доказательство. Оортируем числа из {ai,..., an} в порядке возрастания. Наименьшее число, отсутствующее в этом списке, является решением системы.
Это утверждение показывает, что при сужении единственной NP-полной задачи из [4] на системы линейных дизсравнений по единственному модулю имеет полиномиальный алгоритм решения.
Далее вместо термина «несравнимость» используется термин «дизсравнение» (более удобный, по мнению авторов).
Такой объект исследования, как системы линейных дизсравне- ний, гораздо естественнее для большинства математиков, чем задачи, связанные с проверкой истинности пропозициональной формулы.
В целом полученные результаты показывают, что проверка совместности в целых числах систем линейных дизсравнений может оказаться во многих случаях NP- полной.
Авторы благодарны рецензенту за контрпример к первоначальной формулировке утверждения из введения, позволивший авторам исправить формулировку сужения задачи из этого утверждения.
