ON A TRANSFER THEOREM FOR THE P ≠ NP CONJECTURE

GREGORIO MALAJOVICH

Abstract. A model of computation is defined over the algebraic numbers and over number fields. This model is non-uniform, and the cost of operations depends on the height of the operands and on the degree of the extension of the rational defined by those operands.

A transfer theorem for the P ≠ N PConjecture is proved, namely: P ≠ N Pin this model over the real algebraic numbers if and only if P ≠ N Pin the classical setting.