Журнал СФУ. Математика и физика / Заметка о проблеме равентства P и NP

Полный текст (.pdf)
Номер
Журнал СФУ. Математика и физика. 2021 14 (2)
Авторы
Рыбаков, Владимир В.
Контактная информация
Рыбаков, Владимир В.: Сибирский федеральный университет Красноярск, Российская Федерация; Институт систем информатики им. А. П. Ершова Новосибирск, Российская Федерация
Ключевые слова
deterministic computations; non-deterministic computations; детерминированные вычисления; недетерминитролванные вычисления
Аннотация

В статье вводится алгоритмическая проблема и доказывается, что она разрешима за полиномиальное время на недетерминированных машинах Тьюринга и не решается за полиномиальное время на детерминированных машинах Тьюринга. В то же время, введенная проблема не выглядит как стандартная в общепринятом понимании и не самоочевидно может ли она быть классифицирована как каноническая

Страницы
258–260
DOI
10.17516/1997-1397-2021-14-2-258-260
Статья в архиве электронных ресурсов СФУ
https://elib.sfu-kras.ru/handle/2311/137994