• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文会议>Theory and application of models of computation >Complexity Invariance of Real Interpretations
【24h】

Complexity Invariance of Real Interpretations

机译：真实解释的复杂性不变性

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

摘要

In the field of implicit computational complexity, we are considering in this paper the fruitful branch of interpretation methods. In this area, the synthesis problem is solved by Tarski's decision procedure, and consequently interpretations are usually chosen over the reals rather than over the integers. Doing so, one cannot use anymore the (good) properties of the natural (well-) ordering of N employed to bound the complexity of programs. We show that, actually, polynomials over the reals benefit from some properties that allow their safe use for complexity. We illustrate this by two characterizations, one of PTIME and one of PSPACE.
机译：在隐式计算复杂性领域，我们正在考虑本文中解释方法的卓有成效的分支。在这一领域，综合问题是由塔斯基的决策程序解决的，因此，通常选择的是实数而不是整数。这样做，就无法再使用用来限制程序复杂性的N的自然（良好）排序的（良好）属性。我们表明，实际上，多项式的实数受益于一些属性，这些属性可以安全地用于复杂性。我们通过两种表征来说明这一点，一种是PTIME，另一种是PSPACE。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号