The Foundations of Computation and Complexity Theory over the Reals or an Arbitrary Ring

点击翻译按钮获取中文摘要

Classically, the theories of computation and computational complexity deal with discrete problems. On the other hand, many computational problems have the real numbers as natural domain. A variety of ad hoc methods and models have been employed to analyze complexity issues in this realm, but unlike the classical case, a natural and invariant theory has not yet emerged. This project is pursuing the foundations of a formal theory of computation and complexity over the reals, or an arbitrary ring R. It integrates classical recursive function theory and complexity theory with mainstream algebra, analysis and topology.