...
  • 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>International journal of unconventional computing >Algebraic Characterizations of Complexity-Theoretic Classes of Real Functions
【24h】

Algebraic Characterizations of Complexity-Theoretic Classes of Real Functions

机译：复杂度的代数表征-实函数的理论类

获取原文
获取原文并翻译 | 示例
           
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

Recursive analysis is the most classical approach to model and discuss computations over the real numbers.Recently, it has been shown that com-putability classes of functions in the sense of recursive analysis can be defined (or characterized) in an algebraic machine independent way, without resorting to Turing machines. In particular nice connections between the class of computable functions (and some of its sub- and sup-classes) over the reals and algebraically defined (sub- and sup-) classes of R-recursive functions a la Moore 96 have been obtained. However, until now, this has been done only at the computability level, and not at the complexity level. In this paper we provide a framework that allows us to dive into the complexity level of real functions. In particular we provide the first algebraic characterization of polynomial-time computable functions over the reals. This framework opens the field of implicit complexity of analog functions, and also provides a new reading of some of the existing characterizations at the computability level.
机译：递归分析是对实数进行建模和讨论的最经典方法。最近，研究表明，可以用与代数机器无关的方式定义（或表征）递归分析意义上的可计算函数类，无需诉诸图灵机。特别地，已经获得R递归函数的实数和代数定义的（子和上）类之间的可计算函数的类（及其一些子类和上类）之间的良好联系，从而获得了La Moore 96。但是，到目前为止，这仅在可计算性级别而不是在复杂性级别完成。在本文中，我们提供了一个框架，使我们可以深入研究实际功能的复杂性级别。特别是，我们提供了多项式时间可计算函数在实数上的第一个代数表征。该框架打开了模拟函数隐式复杂性的领域，并在可计算性级别上提供了一些现有特征的新读物。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱：kefu@zhangqiaokeyan.com

京公网安备：11010802029741号 ICP备案号：京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有

  • 客服微信

  • 服务号