- Номер
- Журнал СФУ. Математика и физика. 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
Журнал СФУ. Математика и физика / Заметка о проблеме равентства P и NP
Полный текст (.pdf)