On the P vs NP problem over reals with integer oracle
Alexander Rybalov · 2016
Relativized complexity classes are actively studied in the computation complexity theory since 1975. Classical result of Baker, Gill and Solovay states that there exist two oracles A and B such that PA= NPA, but PB≠ NPB. This result indicates that the classical tools of theory of algorithms (such as diagonalization) are inapplicable to prove the inequality P ≠ NP. We consider a relativised Blum-Shub-Smale model of computations over the field of real numbers. We prove that relativized complexity classes PZand NPZare different in this model, where the oracle Z is the set of integers.