Average-Case Bit-Complexity Theory of Real Functions
Average-Case Bit-Complexity Theory of Real Functions
复制标题
实函数的平均情况位复杂度理论
DOI：
10.1007/978-3-319-32859-1_43
复制
发表时间：
2016
期刊：
影响因子：
--
通讯作者：
M. Ziegler
中科院分区：
文献类型：
--
作者：
M. Schröder;F. Steinberg;M. Ziegler
我们引入并启动了对实数的平均情况位复杂度理论的研究：就像在离散情况下一样，naïve多项式平均运行时间的概念缺乏鲁棒性，因此得到了改进。具有越来越高的最坏情况复杂度的显式连续函数的标准示例实际上是简单的；而另一个例子是用最差和平均复杂性指数构建的：由于拓扑/度量的原因，也就是说，oracle没有帮助。然后将这些概念从实数推广到表征空间；在实际情况中，与随机计算有关。
We introduce, and initiate the study of, average-case bit-complexity theory over the reals: Like in the discrete case a first, naïve notion of polynomial average runtime turns out to lack robustness and is thus refined. Standard examples of explicit continuous functions with increasingly high worst-case complexity are shown to be in fact easy in the mean; while a further example is constructed with both worst and average complexity exponential: for topological/metric reasons, i.e., oracles do not help. The notions are then generalized from the reals to represented spaces; and, in the real case, related to randomized computation.
登录
查看更多内容
DOI：
10.1016/j.ic.2015.03.005
发表时间：
2013
期刊：
Inf. Comput.
影响因子：
--
作者：
V. Brattka;G. Gherardi;R. Hölzl
通讯作者：
R. Hölzl
平滑度的计算优势：解析函数和 Gevrey 层次结构上数值运算符的参数化位复杂度
DOI：
10.1016/j.jco.2015.05.001
发表时间：
2015
期刊：
J. Complex.
影响因子：
--
作者：
A. Kawamura;N. Müller;C. Rösnick;M. Ziegler
通讯作者：
M. Ziegler
关于莱文平均情况复杂性理论的注释
DOI：
10.1007/978-3-642-22670-0_21
发表时间：
1997
期刊：
Electron. Colloquium Comput. Complex.
影响因子：
--
作者：
Oded Goldreich
通讯作者：
Oded Goldreich
表示空间上的概率可计算性概念
影响因子：
--
作者：
Volker Bosserhoff
通讯作者：
Volker Bosserhoff
为什么几乎所有 k-可着色图都很容易着色
影响因子：
0.5
作者：
A. Coja;Michael Krivelevich;Dan Vilenchik
通讯作者：
Dan Vilenchik