Polynomial time computations in models of ET (Q795035)

The paper is devoted to the study of the P\(=NP\) problem. The theory ET (theory of exponential time) introduced by R. A. DeMillo and R. A. Lipton in 1980 is studied. The author discusses polynomial time computations in models of ET and gives examples of simple functions that are not total in \(M_{D\&L}\vDash ET\) as well as predicates in \(P_{D\&L}\) (a class of predicates over \(M_{D\&L})\) that are not computable in \(M_{D\&L}\). The stronger theory ET(Elem) is introduced and sets that are polynomially computable in some model of ET(Elem) are characterized. The last section of the paper is devoted to the following problem: what types of hard sets have arbitrarily long initial segments that can be efficiently decided by short programs. It is shown that it is easily resolved for P and EXP-time complete sets. The question for NP-complete sets is open.