СЛОЖНОСТЬ ЗАДАЧИ РАСПОЗНАВАНИЯ ОДНОГО КЛАССА РЕШЕНИЙ ЛИНЕЙНЫХ УРАВНЕНИЙ
Доказывается NP-полнота задачи распознавания, является ли неотрицательное целочисленноерешение уравнения a1x1 + a2x2 +…+ ak xk = n с натуральными коэффициентами и свободным членом выпуклой комбинацией двух его неотрицательных целочисленных решений. Используется теорема Войгингера об NP-полноте задач...
| Format: | Article |
|---|---|
| Language: | Russian |
| Published: |
National Academy of Sciences of Belarus, the United Institute of Informatics Problems
2018-04-01
|
| Series: | Informatika |
| Online Access: | https://inf.grid.by/jour/article/view/331 |