| |
Вагіс, О. А.
Розв'язність NP-повних задач [Текст] / О. А. Вагіс, А. М. Гупал
// Кібернетика та системний аналіз. – 2022. – Т. 58, № 6. – C. 71- 73.
Аналіз нерозв'язності Діoфантових рівнянь показав, що задачі розпізнавання властивостей класу NP є розв’язуваними, тобто недетермінований алгоритм або повний перебір на вході задачі дає позитивну чи негативну відповідь. Для поліноміальних Діофантових рівнянь такого недетермінованого алгоритму не існує. З нерозв'язності Діофантових рівнянь випливає простий варіант теореми Геделя про неповноту арифметики. |
