Lanean...
СЛОЖНОСТЬ ЗАДАЧИ РАСПОЗНАВАНИЯ ОДНОГО КЛАССА РЕШЕНИЙ ЛИНЕЙНЫХ УРАВНЕНИЙ
Доказывается NP-полнота задачи распознавания, является ли неотрицательное целочисленноерешение уравнения a1x1 + a2x2 +…+ ak xk = n с натуральными коэффициентами и свободным членом выпуклой комбинацией двух его неотрицательных целочисленных решений. Используется теорема Войгингера об NP-полноте задач...
Gorde:
| Formatua: | Artigo |
|---|---|
| Hizkuntza: | Russo |
| Argitaratua: |
The United Institute of Informatics Problems of the National Academy of Sciences of Belarus
2018-04-01
|
| Saila: | Informatika |
| Sarrera elektronikoa: | https://inf.grid.by/jour/article/view/331 |
| Etiketak: |
Etiketa erantsi
Etiketarik gabe, Izan zaitez lehena erregistro honi etiketa jartzen!
|