I tiakina i:
| Kaituhi matua: | |
|---|---|
| Hōputu: | Preprint |
| I whakaputaina: |
1999
|
| Ngā marau: | |
| Urunga tuihono: | https://arxiv.org/abs/math/9904130 |
| Ngā Tūtohu: |
Tāpirihia he Tūtohu
Kāore He Tūtohu, Me noho koe te mea tuatahi ki te tūtohu i tēnei pūkete!
|
Rārangi ihirangi:
- 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 $τ$-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.