direkt zum Inhalt springen

direkt zum Hauptnavigationsmenü

Sie sind hier

TU Berlin

Page Content

There is no English translation for this web page.

Search for Publication

Search for publications




All Publications

On Implications between P-NP-Hypotheses: Decision versus Computation in Algebraic Complexity
Citation key B-On-Implications-Between-P-Np-Hypotheses-Decision-Versus-Computation-In-Algebraic-Complexity
Author Peter Bürgisser
Title of Book Proc. 26th Symposium on Mathematical Foundations of Computer Science
Pages 3-17
Year 2001
Address Marianske Lazne
Number 2136
Note (invited paper)
Publisher Springer Verlag
Series Lecture Notes in Computer Science
Abstract 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.
Link to publication Link to original publication Download Bibtex entry

Zusatzinformationen / Extras

Quick Access:

Schnellnavigation zur Seite über Nummerneingabe

This site uses Matomo for anonymized webanalysis. Visit Data Privacy for more information and opt-out options.