Topics in real and complex number complexity theory
Martijn Baartse, Klaus Meer · Contemporary mathematics - American Mathematical Society · 2013
The paper intends to introduce into topics relevant in real and complex number complexity theory. This is done in a survey style. Taking as starting point the computational model introduced by Blum, Shub, and Smale the following issues are addressed: Basic results concerning decidability and N P \mathrm {NP} -completeness, transfer results of open questions between different models of computation, structural complexity inside N P R \mathrm {NP}_{\mathbb {R}} , computational universality, and probabilistically checkable proofs over the real and complex numbers.