Original scientific paper
SIGMA-NOTATION AND THE EQUIVALENCE OF P AND NP CLASSES
Miron I. Telpiz
; Tarusa, Russia
Abstract
The aim of this paper is to show that σ–notation, based on the positionality principle, doesn’t just answer the question of equivalence of P and NP problem classes, but also represents the key to the solution of (some) more general problems from the domain of multivalued logics. However, the achievement of such an aim in its full scope is hardly possible within the limits of this paper. Therefore, the following plan shall be realized: Firstly, the logic algebra fragment necessary for the solution of the P and NP classes equivalence problem shall be expounded. Secondly, the necessary symbols and definitions shall be introduced to show that the calculations in the domain of the multivalued logic can be directly executed within the framework of σ–notation.
Keywords
σ-notation; P=NP problem; SAT problem; multivalued logics
Hrčak ID:
78237
URI
Publication date:
21.12.2005.
Visits: 877 *