📄Работа №130961
Тема: УСЛОВИЯ NP-ПОЛНОТЫ ПРОВЕРКИ СОВМЕСТНОСТИ НЕСКОЛЬКИХ ВИДОВ СИСТЕМ ЛИНЕЙНЫХ ДИОФАНТОВЫХ ДИЗУРАВНЕНИЙ
Тип работы
Диссертация
Предмет
математика
Объем:
7 листов
Год:
2016
Просмотров:
77
770
руб.
🛒 Купить работу
Не подходит эта работа?
Закажите новую по вашим требованиям
Узнать цену на написание
Закажите новую по вашим требованиям
Представленный материал является образцом учебного исследования, примером структуры и содержания учебного исследования по заявленной теме. Размещён исключительно в информационных и ознакомительных целях.
Workspay.ru оказывает информационные услуги по сбору, обработке и структурированию материалов в соответствии с требованиями заказчика.
Размещение материала не означает публикацию произведения впервые и не предполагает передачу исключительных авторских прав третьим лицам.
Материал не предназначен для дословной сдачи в образовательные организации и требует самостоятельной переработки с соблюдением законодательства Российской Федерации об авторском праве и принципов академической добросовестности.
Авторские права на исходные материалы принадлежат их законным правообладателям. В случае возникновения вопросов, связанных с размещённым материалом, просим направить обращение через форму обратной связи.
Настоящий учебно-методический информационный материал размещён в ознакомительных и исследовательских целях и представляет собой пример учебного исследования. Не является готовым научным трудом и требует самостоятельной переработки.
📋 Содержание
АННОТАЦИЯ 1
ВВЕДЕНИЕ 1
1. СИСТЕМЫ ЛИНЕЙНЫХ ДИЗУРАВНЕНИЙ 1
ЗАКЛЮЧЕНИЕ 4
ЛИТЕРАТУРА 5
ANNOTATION 6
REFERENCES 6
ВВЕДЕНИЕ 1
1. СИСТЕМЫ ЛИНЕЙНЫХ ДИЗУРАВНЕНИЙ 1
ЗАКЛЮЧЕНИЕ 4
ЛИТЕРАТУРА 5
ANNOTATION 6
REFERENCES 6
📖 Введение
Настоящая статья является продолжением статей [1, 2], опубликованных в предыдущих выпусках журнала и посвящённых условиям NP-полноты проверки совместности систем линейных диофантовых дизсравнений, сравнений и уравнений. Ниже предлагаются серии теоретико-числовых задач, связанных с системами линейных диофантовых дизуравнений, с явно выделенными параметрами, и доказываются условия на параметры, при выполнении которых каждая задача серии NP- полна.
Термин «дизуравнение» используется ниже для линейных соотношений, в которых левая часть не равна правой, в отличие от термина «неравенство», который традиционно предполагает в соотношениях знаки <, >, < или >. Это понятие тесно связано с понятием «уравнение» и в значительной степени является двойственным к нему.
Рассматриваемые задачи тесно связаны с задачами из [3-10].
Термин «дизуравнение» используется ниже для линейных соотношений, в которых левая часть не равна правой, в отличие от термина «неравенство», который традиционно предполагает в соотношениях знаки <, >, < или >. Это понятие тесно связано с понятием «уравнение» и в значительной степени является двойственным к нему.
Рассматриваемые задачи тесно связаны с задачами из [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].
Полученные результаты дополняют результаты, полученные в [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].
ИЛИ
Поиск аналога
📕 Список литературы
🖼 Скриншоты
🛒 Оформить заказ
⚡ Работу высылаем в течении 5 минут после оплаты.