Programmability and P=NP conjecture

Article type: Research Article

Authors: Radziszowski, Stanisław

Affiliations: University of Warsaw

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

Keywords: time complexity, Turing machine, programmability, nondeterminism

DOI: 10.3233/FI-1978-2106

Journal: Fundamenta Informaticae, vol. 2, no. 1, pp. 71-82, 1978