Research output: Contribution to journal › Article › peer-review
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.
| Original language | English |
|---|---|
| Pages (from-to) | 18-22 |
| Number of pages | 5 |
| Journal | Vestnik St. Petersburg University: Mathematics |
| Volume | 49 |
| Issue number | 1 |
| DOIs | |
| State | Published - 1 Jan 2016 |
ID: 46401993