Ultimate Polynomial Time

Abstract

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.

Cited by in corpus (1)

• Lower bounds for some decision problems over C