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 $P = N P$ problem in that system to the classical $P = N P$ problem for Turing machines. This implies that the $P = N P$ problem can be solved in thc theory of programs in some relational systems.

Keywords

time complexity Turing machine programmability nondeterminism

Get full access to this article

View all access options for this article.