Тип публикации: статья из журнала
Год издания: 2021
Идентификатор DOI: 10.17516/1997-1397-2021-14-2-258-260
Ключевые слова: deterministic computations, non-deterministic computations
Аннотация: We find a computational algorithmic task and prove that it is solvable in polynomial time by a non-deterministic Turing machine and cannot be solved in polynomial time by any deterministic Turing machine. The point is that our task does not look as very canonical one and if it may be classified as computational problem in standard Показать полностьюterms. © Siberian Federal University. All rights reserved.
Журнал: Journal of Siberian Federal University - Mathematics and Physics
Выпуск журнала: Vol. 14, Is. 2
Номера страниц: 258-260
ISSN журнала: 19971397
Издатель: Siberian Federal University