Programmability and P = N P conjecture

Abstract

We define the time-complexity of programs (FS-expressions) in an arbitrary relational system. We extend these notions to nondeterministic programs (NFS-expressions). There are some sufficient conditions for a relational system which ensure the equivalence of the $\mathit{P}=\mathit{N}\mathit{P}$ problem in that system to the classical $\mathit{P}=\mathit{N}\mathit{P}$ problem for Turing machines. This implies that the $\mathit{P}=\mathit{N}\mathit{P}$ problem can be solved in thc theory of programs in some relational systems.