Тема: УСЛОВИЯ NP-ПОЛНОТЫ ПРОВЕРКИ СОВМЕСТНОСТИ НЕСКОЛЬКИХ ВИДОВ СИСТЕМ ЛИНЕЙНЫХ ДИОФАНТОВЫХ ДИЗСРАВНЕНИЙ

Ценность формулировки и доказательств 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- полной.
Авторы благодарны рецензенту за контрпример к первоначальной формулировке утверждения из введения, позволивший авторам исправить формулировку сужения задачи из этого утверждения.
Купить