来自杂志 Forum of Mathematics, Sigma 的文献。
当前共找到 1 篇文献分享。
1.
林海onrush (2023-06-30 23:49):
#paper,doi:10.1017/fms.2015.2,A THEORY OF COMPLEXITY,CONDITION,AND ROUNDOFF,计算复杂性理论作为评判算法的重要标准,研究各种复杂性类的范围问题具有数学和工程意义,作者开发了一个理论的复杂性数值计算,考虑到输入数据的条件,并允许舍入的计算。Shub和Smale在R上的计算 (这又遵循了由Cook、Karp和Levin等人提出的经典、离散、复杂性理论)。特别专注于决策问题的复杂性类,不同版本的P,NP和EXP的多项式和非确定性多项式。及指数时间。作者证明了这些复杂性类之间的一些基本关系,并提供自然NP完全问题。
Abstract:
We develop a theory of complexity for numerical computations that takes into account the condition of the input data and allows for roundoff in the computations. We follow the lines … >>>
We develop a theory of complexity for numerical computations that takes into account the condition of the input data and allows for roundoff in the computations. We follow the lines of the theory developed by Blum, Shub and Smale for computations over $\mathbb{R}$ (which in turn followed those of the classical, discrete, complexity theory as laid down by Cook, Karp, and Levin, among others). In particular, we focus on complexity classes of decision problems and, paramount among them, on appropriate versions of the classes $\mathsf{P}$, $\mathsf{NP}$, and $\mathsf{EXP}$ of polynomial, nondeterministic polynomial, and exponential time, respectively. We prove some basic relationships between these complexity classes, and provide natural NP-complete problems. <<<
翻译
回到顶部