Сибирский федеральный университет

Тип публикации: статья из журнала

Год издания: 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

• Rybakov Vladimir V. (Siberian Fed Univ, Krasnoyarsk, Russia; AP Ershov Inst Informat Syst, Novosibirsk, Russia)

• Scopus
• Web of Science Core Collection
• Ядро РИНЦ (eLIBRARY.RU)