RUS  ENG
Полная версия
ЖУРНАЛЫ // Журнал Сибирского федерального университета. Серия «Математика и физика» // Архив

Журн. СФУ. Сер. Матем. и физ., 2021, том 14, выпуск 2, страницы 258–260 (Mi jsfu911)

A short essay towards if $P$ not equal $NP$

[Заметка о проблеме равенства $P$ и $NP$]

Vladimir V. Rybakovab

a Siberian Federal University, Krasnoyarsk, Russian Federation
b A. P. Ershov Institute of Informatics Systems, Novosibirsk, Russian Federation

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

Ключевые слова: детерминированные вычисления, недетерминированные вычисления.

УДК: 512.54

Получена: 10.12.2020
Исправленный вариант: 10.01.2021
Принята: 12.02.2020

Язык публикации: английский

DOI: 10.17516/1997-1397-2021-14-2-258-260



Реферативные базы данных:


© МИАН, 2024