Descriptive complexity theory over the real numbers
Descriptive complexity theory over the real numbers
复制标题
实数的描述复杂性理论
DOI：
--
复制
发表时间：
1995
期刊：
影响因子：
--
通讯作者：
K. Meer
中科院分区：
文献类型：
--
作者：
E. Grädel;K. Meer
我们提出了一种关于Blum， Shub和Smale模型的实数复杂性的逻辑方法。所考虑的逻辑是在一类特殊的两排序结构上解释的，称为r结构，它们由有限结构与实数的有序域和有限结构到r的有限函数集组成，它们是最近由Gradel和Gurevich引入的元zite结构的一种特殊情况。我们认为r结构提供了正确的结构类别来发展r的描述性复杂性理论。我们通过将r结构上的逻辑可定义性与bss机器的计算复杂性联系起来的一些结果来证实这一说法。
We present a logical approach to complexity over the real numbers with respect to the model of Blum, Shub and Smale. The Iogics under consideration are interpreted over a special class of two-sorted structures, called R-structures They consist of a finite structure together with the ordered field of reals and a finite set of functions from the finite structure into R. They are a special case of the metaj%zite structures introduced recently by Gradel and Gurevich. We argue that R-structures provide the right class of structures to develop a descriptive complexity theory over R. We substantiate this claim by a number of results that relate logical definability on R-structures with complexity of computations of BSS-machines.