| Zitatschlüssel |
B-On-Implications-Between-P-Np-Hypotheses-Decision-Versus-Computation-In-Algebraic-Complexity |
| Autor |
Peter Bürgisser |
| Buchtitel |
Proc. 26th Symposium on Mathematical Foundations of Computer Science |
| Seiten |
3-17 |
| Jahr |
2001 |
| Adresse |
Marianske Lazne |
| Nummer |
2136 |
| Notiz |
(invited paper) |
| Verlag |
Springer Verlag |
| Serie |
Lecture Notes in Computer Science |
| Zusammenfassung |
Several models of $NP$-completeness in an algebraic framework of computation have been proposed in the past, each of them hinging on a fundamental hypothesis of type $P\ne NP$. We first survey some known implications between such hypotheses and then describe attempts to establish further connections. This leads us to the problem of relating the complexity of computational and decisional tasks and naturally raises the question about the connection of the complexity of a polynomial with those of its factors. After reviewing what is known with this respect, we discuss a new result involving a concept of approximative complexity. |
