ULTIMATE POLYNOMIAL TIME

GREGORIO MALAJOVICH

Abstract. The class UP of ‘ultimate polynomial time’ problems over ℂ is introduced; it contains the class P of polynomial time problems over ℂ.

The τ-Conjecture for polynomials implies that UP does not contain the class of non-deterministic polynomial time problems definable without constants over ℂ. This latest statement implies that P ≠ N P over ℂ.

A notion of ‘ultimate complexity’ of a problem is suggested. It provides lower bounds for the complexity of structured problems.