Home > Library > MSRI Preprints > 1999 > Preprint 1999-003 > Abstract

Abstract for MSRI Preprint 1999-003

Ultimate Polynomial Time

Gregorio Malajovich

The class $\mathcal{UP}$ of "ultimate polynomial time" problems over $\mathbb C$ is introduced; it contains the class $\mathcal P$ of polynomial time problems over $\mathbb C$.

The $\tau$-Conjecture for polynomials implies that $\mathcal{UP}$ does not contain the class of non-deterministic polynomial time problems definable without constants over $\mathbb C$. This latest statement implies that $\mathcal P \ne \mathcal{NP}$ over $\mathbb C$.

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