Standard

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

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

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

Harvard

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

APA

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

Vancouver

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

Author

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

BibTeX

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

}

RIS

TY - JOUR

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

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

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

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

PY - 2016

Y1 - 2016

N2 - В статье предлагаются три серии теретико-числовых задач с явно выделенными параметрами, касающиеся систем сравнений по модулю $m$ и систем диофантовых уравнений с решениями из заданного отрезка. Доказываются ограничения на параметры, при выполнении которых любая задача каждой серии NP-полна. Доказывается, что при любых $m_1$ и $m_2$ ($m_12$ задача проверки совместности на подмножестве, содержащем по крайней мере 2 элемента, множества $\{ 0, ... , m-1 \}$ системы линейных сравнений по модулю $m$, каждое из которых содержит ровно 3 переменные, NP-полна. Для систем линейных диофантовых уравнений, каждое из которых содержит ровно 3 переменные, доказана NP-полнота задачи проверки их совместности на заданном отрезке целых чисел.Эта задача допускает также и простую геометрическую и

AB - В статье предлагаются три серии теретико-числовых задач с явно выделенными параметрами, касающиеся систем сравнений по модулю $m$ и систем диофантовых уравнений с решениями из заданного отрезка. Доказываются ограничения на параметры, при выполнении которых любая задача каждой серии NP-полна. Доказывается, что при любых $m_1$ и $m_2$ ($m_12$ задача проверки совместности на подмножестве, содержащем по крайней мере 2 элемента, множества $\{ 0, ... , m-1 \}$ системы линейных сравнений по модулю $m$, каждое из которых содержит ровно 3 переменные, NP-полна. Для систем линейных диофантовых уравнений, каждое из которых содержит ровно 3 переменные, доказана NP-полнота задачи проверки их совместности на заданном отрезке целых чисел.Эта задача допускает также и простую геометрическую и

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

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

KW - принадлежность целочисленной точки из ограниченной области пересечению гиперплоскостей

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

M3 - статья

VL - 3 (61)

SP - 198 — 203

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

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

SN - 1025-3106

IS - 2

ER -

ID: 7591720