Some questions of the theory of computational complexity from the point of view of elementary theory of models

The presented study considers one of the most famous problems of computational complexity theory: what is the ratio of complexity classes NP and co NP? To answer this question, the well-known fundamental concept of model completeness of the theory under study, a section of mathematics Model Theory , was rethought and reformulated accordingly. The purpose of reformulating this fundamental concept was to describe the ratio of complexity classes NP and co NP, from a model-theoretical point of view. It is a well-known fact: the hierarchy of properties in any model of a model-complete theory breaks o at the rst level. This key idea has been the basis for a fruitful study of the relationship between the complexity classes NP and co NP. It is a well-known fact that there exists an oracle A such that the complexity class NP(A) di ers from the complexity class co NP(A). By developing oracle computations in an appropriate manner and formalizing them in the class of primitive recursive algorithms, and then using the theoretical-model relationship between the speci ed classes, it was possible to relate the relationship between the complexity classes of computations NP and co NP with the relationship between the complexity classes NP(A) and co NP(A), which then made it possible to establish that the complexity class NP is not a Boolean algebra. In formalizing oracle computations in the class of primitive recursive algorithms, a number of interesting theorems were proved, one of which is an analogue of the xed point theorem, which was used in the key theorem that allowed establishing that the complexity class NP is not a Boolean algebra. After reading the presented research, one can understand why the relativization e ect prevents one from obtaining high lower bounds or separating one complexity class from another complexity class of computations using the methods of "Discrete Mathematics" The presented study is original, and many important concepts that are used in this study have not been encountered in any studies known to me