Standard

Условия NP-полноты проверки совместности нескольких видов систем линейных диофантовых дизсравнений. / Косовский, Н.К.; Косовская, Т.М.; Косовский, Н.Н.

в: ВЕСТНИК САНКТ-ПЕТЕРБУРГСКОГО УНИВЕРСИТЕТА. СЕРИЯ 1: МАТЕМАТИКА, МЕХАНИКА, АСТРОНОМИЯ, Том 3(.61), № 1, 2016, стр. 196 — 201.

Результаты исследований: Научные публикации в периодических изданиях › статья › Рецензирование

Harvard

Косовский, НК, Косовская, ТМ & Косовский, НН 2016, 'Условия NP-полноты проверки совместности нескольких видов систем линейных диофантовых дизсравнений', ВЕСТНИК САНКТ-ПЕТЕРБУРГСКОГО УНИВЕРСИТЕТА. СЕРИЯ 1: МАТЕМАТИКА, МЕХАНИКА, АСТРОНОМИЯ, Том. 3(.61), № 1, стр. 196 — 201..

APA

Косовский, Н. К., Косовская, Т. М., & Косовский, Н. Н. (2016). Условия NP-полноты проверки совместности нескольких видов систем линейных диофантовых дизсравнений. ВЕСТНИК САНКТ-ПЕТЕРБУРГСКОГО УНИВЕРСИТЕТА. СЕРИЯ 1: МАТЕМАТИКА, МЕХАНИКА, АСТРОНОМИЯ, 3(.61)(1), 196 — 201..

Vancouver

Косовский НК, Косовская ТМ, Косовский НН. Условия NP-полноты проверки совместности нескольких видов систем линейных диофантовых дизсравнений. ВЕСТНИК САНКТ-ПЕТЕРБУРГСКОГО УНИВЕРСИТЕТА. СЕРИЯ 1: МАТЕМАТИКА, МЕХАНИКА, АСТРОНОМИЯ. 2016;3(.61)(1):196 — 201.

Author

Косовский, Н.К. ; Косовская, Т.М. ; Косовский, Н.Н. / Условия NP-полноты проверки совместности нескольких видов систем линейных диофантовых дизсравнений. в: ВЕСТНИК САНКТ-ПЕТЕРБУРГСКОГО УНИВЕРСИТЕТА. СЕРИЯ 1: МАТЕМАТИКА, МЕХАНИКА, АСТРОНОМИЯ. 2016 ; Том 3(.61), № 1. стр. 196 — 201.

BibTeX

@article{e555e725e4044c49bcabd3b9eed47cf2,
title = "Условия NP-полноты проверки совместности нескольких видов систем линейных диофантовых дизсравнений",
abstract = "В статье предлагаются две серии теретико-числовых задач с явно выделенными параметрами, касающиеся дизсравнений по модулю m. Доказываются ограничения на параметры, при выполнении которых любая задача каждой серии NP-полна. Доказывается, что при всяком m>2 задача проверки совместности системы линейных дизсравнений по модулю m, каждое из которых содержит ровно 3 переменные (даже если коэффициенты при них из {-1,1}), NP-полна. Также доказывается, что при всяком m>3 задача проверки совместности системы линейных дизсравнений по модулю m, каждое из которых содержит ровно 2 переменные, NP-полна. Если P \neq NP, то формулировки доказанных теорем не могут быть изменены путём замены термина > на термин >.",
keywords = "система линейных диофантовых дизсравнений, NP-полнота.",
author = "Н.К. Косовский and Т.М. Косовская and Н.Н. Косовский",
year = "2016",
language = "русский",
volume = "3(.61)",
pages = "196 — 201.",
journal = "ВЕСТНИК САНКТ-ПЕТЕРБУРГСКОГО УНИВЕРСИТЕТА. МАТЕМАТИКА. МЕХАНИКА. АСТРОНОМИЯ",
issn = "1025-3106",
publisher = "Издательство Санкт-Петербургского университета",
number = "1",

}

RIS

TY - JOUR

T1 - Условия NP-полноты проверки совместности нескольких видов систем линейных диофантовых дизсравнений

AU - Косовский, Н.К.

AU - Косовская, Т.М.

AU - Косовский, Н.Н.

PY - 2016

Y1 - 2016

N2 - В статье предлагаются две серии теретико-числовых задач с явно выделенными параметрами, касающиеся дизсравнений по модулю m. Доказываются ограничения на параметры, при выполнении которых любая задача каждой серии NP-полна. Доказывается, что при всяком m>2 задача проверки совместности системы линейных дизсравнений по модулю m, каждое из которых содержит ровно 3 переменные (даже если коэффициенты при них из {-1,1}), NP-полна. Также доказывается, что при всяком m>3 задача проверки совместности системы линейных дизсравнений по модулю m, каждое из которых содержит ровно 2 переменные, NP-полна. Если P \neq NP, то формулировки доказанных теорем не могут быть изменены путём замены термина > на термин >.

AB - В статье предлагаются две серии теретико-числовых задач с явно выделенными параметрами, касающиеся дизсравнений по модулю m. Доказываются ограничения на параметры, при выполнении которых любая задача каждой серии NP-полна. Доказывается, что при всяком m>2 задача проверки совместности системы линейных дизсравнений по модулю m, каждое из которых содержит ровно 3 переменные (даже если коэффициенты при них из {-1,1}), NP-полна. Также доказывается, что при всяком m>3 задача проверки совместности системы линейных дизсравнений по модулю m, каждое из которых содержит ровно 2 переменные, NP-полна. Если P \neq NP, то формулировки доказанных теорем не могут быть изменены путём замены термина > на термин >.

KW - система линейных диофантовых дизсравнений

KW - NP-полнота.

M3 - статья

VL - 3(.61)

SP - 196 — 201.

JO - ВЕСТНИК САНКТ-ПЕТЕРБУРГСКОГО УНИВЕРСИТЕТА. МАТЕМАТИКА. МЕХАНИКА. АСТРОНОМИЯ

JF - ВЕСТНИК САНКТ-ПЕТЕРБУРГСКОГО УНИВЕРСИТЕТА. МАТЕМАТИКА. МЕХАНИКА. АСТРОНОМИЯ

SN - 1025-3106

IS - 1

ER -

ID: 7591689