КіСА | Зміст

Том 58 >>> № 6 ЛИСТОПАД — ГРУДЕНЬ 2022

-->

УДК 519.217.2

О.А. ВАГІС,
Інститут кібернетики ім. В.М. Глушкова НАН України, Київ, Україна,
valexdep135@gmail.com

А.М. ГУПАЛ,
Інститут кібернетики ім. В.М. Глушкова НАН України, Київ, Україна,
gupalanatol@gmail.com

РОЗВ’ЯЗНІСТЬ NP-ПОВНИХ ЗАДАЧ

Анотація. Аналіз нерозв’язності Діoфантових рівнянь показав, що задачі розпізнавання властивостей класу NP є розв’язуваними, тобто недетермінований алгоритм або повний перебір на вході задачі дає позитивну чи негативну відповідь. Для поліноміальних Діофантових рівнянь такого недетермінованого алгоритму не існує. З нерозв’язності Діофантових рівнянь випливає простий варіант теореми Геделя про неповноту арифметики.

Ключові слова: NP-повні задачі, Діофантові множини, недетермінований алгоритм.

ПОВНИЙ ТЕКСТ

СПИСОК ЛІТЕРАТУРИ

Гэри М., Джонсон Л. Вычислительные машины и труднорешаемые задачи. Москва: Мир, 1982. 416 с.

Cook S.A. The complexity of theorem-proving procedures. Proc. 3 rd Ann. ACM Symp. on Theory of Computing Association for Computing Machinery. New York. 1971. Р. 151–158.

Матиясевич Ю.В. Диофантовы множнства. Успехи математических наук. 1971. Т. 22. Вып. 5. С. 185–222.

Катленд Н. Вычислимость. Введение в теорию рекурсивных функций. Москва: Мир, 1983. 256 с.