Siberian Federal University 
- Issue
- Journal of Siberian Federal University. Mathematics & Physics. 2021 14 (2)
- Authors
- Rybakov, Vladimir V.
- Contact information
- Rybakov, Vladimir V.: Siberian Federal University Krasnoyarsk, Russian Federation; A.P. Ershov Institute of Informatics Systems Novosibirsk, Russian Federation;
- Keywords
- deterministic computations; non-deterministic computations
- Abstract
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
- Pages
- 258–260
- DOI
- 10.17516/1997-1397-2021-14-2-258-260
- Paper at repository of SibFU
- https://elib.sfu-kras.ru/handle/2311/137994
Journal of Siberian Federal University. Mathematics & Physics / A Short Essay towards if P not equal NP
Full text (.pdf)