Настоящая статья является продолжением статей [1, 2], опубликованных в предыдущих выпусках журнала и посвящённых условиям NP-полноты проверки совместности систем линейных диофантовых дизсравнений, сравнений и уравнений. Ниже предлагаются серии теоретико-числовых задач, связанных с системами линейных диофантовых дизуравнений, с явно выделенными параметрами, и доказываются условия на параметры, при выполнении которых каждая задача серии NP- полна.
Термин «дизуравнение» используется ниже для линейных соотношений, в которых левая часть не равна правой, в отличие от термина «неравенство», который традиционно предполагает в соотношениях знаки <, >, < или >. Это понятие тесно связано с понятием «уравнение» и в значительной степени является двойственным к нему.
Рассматриваемые задачи тесно связаны с задачами из [3-10].
Граница между полиномиальными (по числу шагов при реализации на машине Тьюринга) и сверхполиномиальными оценками в настоящее время является точкой роста доказательства новых математических теорем. Такие теоремы представляют непосредственный практический интерес для разработчиков программ, реализующих разнообразные математические алгоритмы.
Полученные результаты дополняют результаты, полученные в [13].
Сформулированная в следствии теоремы 3 NP-полная задача является одной из наиболее простых теоретико-числовых NP-полных задач, поскольку исключение из неё всех сравнений по модулю 2 (или всех сравнений по модулю 3) обеспечивает её решение полиномиальным по времени алгоритмом (методом исключения неизвестных). Речь идёт ободной и той же системе, проверяемой на наличие общего решения как по модулю 2, так и по модулю 3.
Отметим, что NP-полнота каждой задачи серии задач Система линейных 3-дизуравнений [m, m'] (при m' > m) имеет практическое значение. Поскольку множество значений переменной компьютерного типа integer может рассматриваться как целочисленные значения отрезка, теорема 3 доказывает неполиномиальность любого алгоритма решения таких систем в множестве чисел типа integer, если справедливо P/NP. Тем не менее, если средства программирования имеют встроенные операции со сколь угодно длинными целыми числами, имеется полиномиальный алгоритм решения рассматриваемых систем в таких целых числах. Подобными средствами обладают все диалекты языка рефал (см., например, [14]). Таким образом, можно сформулировать следующую рекомендацию разработчикам программного продукта: не надеяться на приемлемое время нахождения точного решения системы из описанных множеств систем линейных уравнений при решении их в числах типа integer, а использовать представления сколь угодно длинных натуральных чисел или языки, в которых встроены операции с такими числами (при этом, естественно, время, затрачиваемое на выполнение одной арифметической операции увеличивается полиномиально от длины записи аргументов).
Каждая задача серий как Система линейных 3-дизуравнений на отрезке целых чисел [m, m'], так и 2-дизуравнений (при m' > m + 2) имеет простую теоретико-числовую формулировку, позволяющую её использовать для доказательства NP-полноты почти всех NP-полных задач.
Если справедливо P/NP, формулировки теорем 1-3 не могут быть изменены путём замены терминов «2-дизуравнение» и «3-дизуравнение» на термины «1- дизуравнение» и «2-дизуравнение» соответственно.
Теоремы 1 и 3 анонсированы в [15].
