Computations over Z and R : a comparison
- Regarding real number models of computation may be a helpful way to get deeper insight into the classical theory over Z. Therefore it seems useful to study the complexity of classical problems in the real model. In this connection, the problem of deciding the existence of a nonnegative zero for certain polynomials plays an important part because a lot of NP-problems over Z can be polynomial reduced to it.
Author: | Klaus MeerGND |
---|---|
URL: | http://www.sciencedirect.com/science/article/pii/0885064X90900226 |
DOI: | https://doi.org/10.1016/0885-064X(90)90022-6 |
ISSN: | 0885-064X |
Title of the source (English): | Journal of Complexity |
Document Type: | Scientific journal article peer-reviewed |
Language: | English |
Year of publication: | 1990 |
Volume/Year: | 6 |
Issue number: | 3 |
First Page: | 256 |
Last Page: | 263 |
Faculty/Chair: | Fakultät 1 MINT - Mathematik, Informatik, Physik, Elektro- und Informationstechnik / FG Theoretische Informatik |