Geodesic
A short essay towards if $P$ not equal $NP$
Žurnal Sibirskogo federalʹnogo universiteta. Matematika i fizika, Tome 14 (2021) no. 2, pp. 258-260 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

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.
Keywords: deterministic computations, non-deterministic computations. 
@article{JSFU_2021_14_2_a13,
     author = {Vladimir V. Rybakov},
     title = {A short essay towards if $P$ not equal $NP$},
     journal = {\v{Z}urnal Sibirskogo federalʹnogo universiteta. Matematika i fizika},
     pages = {258--260},
     year = {2021},
     volume = {14},
     number = {2},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/JSFU_2021_14_2_a13/}
}
TY  - JOUR
AU  - Vladimir V. Rybakov
TI  - A short essay towards if $P$ not equal $NP$
JO  - Žurnal Sibirskogo federalʹnogo universiteta. Matematika i fizika
PY  - 2021
SP  - 258
EP  - 260
VL  - 14
IS  - 2
UR  - http://geodesic.mathdoc.fr/item/JSFU_2021_14_2_a13/
LA  - en
ID  - JSFU_2021_14_2_a13
ER  - 
%0 Journal Article
%A Vladimir V. Rybakov
%T A short essay towards if $P$ not equal $NP$
%J Žurnal Sibirskogo federalʹnogo universiteta. Matematika i fizika
%D 2021
%P 258-260
%V 14
%N 2
%U http://geodesic.mathdoc.fr/item/JSFU_2021_14_2_a13/
%G en
%F JSFU_2021_14_2_a13
Vladimir V. Rybakov. A short essay towards if $P$ not equal $NP$. Žurnal Sibirskogo federalʹnogo universiteta. Matematika i fizika, Tome 14 (2021) no. 2, pp. 258-260. http://geodesic.mathdoc.fr/item/JSFU_2021_14_2_a13/

[1] S.A. Cook, “The complexity of theorem proving procedures”, Proceedings of the Third Annual ACM Symposium on Theory of Computing, 1971, 151–158 | DOI | MR | Zbl

[2] https://en.wikipedia.org/wiki/P_versus_NP_problem

[3] Javier A. Arroyo-Figueroa, The Existence of the Tau One-Way Functions Class as a Proof that P!= NP, 2016, arXiv: 1604.03758

[4] Mathias Hauptmann, On Alternation and the Union Theorem, Mathematics, Computer Science, 2016, arXiv: 1602.04781