NP completeness conditions for verifying the consistency of several kinds of systems of linear diophantine discongruences

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

2 Цитирования (Scopus)

Аннотация

We propose two series of number-theory problems with explicitly marked out parameters related to discongruences modulo m. We find parameter constraints that provide the NP completeness for any problem of every series. For any m > 2, we prove the NP completeness of the verification problem for the consistency of a system of linear discongruences modulo m such that any discongruence contains exactly three variables, including the case where its coefficients belong to {–1, 1}. For any m > 3, we prove the NP completeness of the verification problem for the consistency of a system of linear discongruences modulo m such that any discongruence contains exactly 2 variables. If P ≠ NP, then one cannot change the term 2-discongruence for the term 1-discongruence in the statements of the proven theorems.

Язык оригиналаанглийский
Страницы (с-по)18-22
Число страниц5
ЖурналVestnik St. Petersburg University: Mathematics
Том49
Номер выпуска1
DOI
СостояниеОпубликовано - 1 янв 2016

Предметные области Scopus

  • Математика (все)

Fingerprint Подробные сведения о темах исследования «NP completeness conditions for verifying the consistency of several kinds of systems of linear diophantine discongruences». Вместе они формируют уникальный семантический отпечаток (fingerprint).

  • Цитировать