### Аннотация

Three series of number-theoretic problems with explicitly marked parameters that concerning systems of modulo m congruences and systems of Diophantine equations with solutions from the given segment are proposed. Parameter constraints such that any problem of each series is NP complete when they are met are proved. For any m_{1} and m_{2} (m_{1} < m_{2} and m1 is not a divisor of m_{2}), the verification problem for the consistency of a system of linear congruences modulo m_{1} and m_{2} simultaneously, each containing exactly three variables, is proved to be NP complete. In addition, for any m > 2, the verification problem for the consistency on the subset, containing at least two elements, of the set {0, …, m–1} for the system of linear congruences modulo m, each of which contains exactly three variables, is proved to be NP complete. If P ≠ NP, one cannot replace the term 3-discongruence with the term 2-discongruence in the statement of the theorem. For systems of Diophantine linear equations, each of which contains exactly three variables, the verification problem for their consistency on the given segment of integers is proved to be NP complete. If P ≠ NP, one cannot replace the term 3-equation with the term 2-equation in the statement of the theorem. This problem can also have a simple geometrical interpretation concerning the NP completeness of the verification problem on whether there an integer point of intersection of the given hyperplanes exists that cuts off equivalent segments on three axes and are parallel to other axes inside of a multidimensional cube. The problems of the stated series include practically useful problems. Since the range of values for an integer computer variable can be considered integer values from a segment, if P ≠ NP, theorem 5 proves that any algorithm that solves these systems in the set of numbers of the integer type is nonpolynomial [6].

Язык оригинала | английский |
---|---|

Страницы (с-по) | 111-114 |

Число страниц | 4 |

Журнал | Vestnik St. Petersburg University: Mathematics |

Том | 49 |

Номер выпуска | 2 |

DOI | |

Состояние | Опубликовано - 1 апр 2016 |

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

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

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

## Цитировать

*Vestnik St. Petersburg University: Mathematics*,

*49*(2), 111-114. https://doi.org/10.3103/S1063454116020084