Using Depth to Capture Average-Case Complexity
Using Depth to Capture Average-Case Complexity
复制标题
使用深度来捕获平均情况的复杂性
DOI：
--
复制
发表时间：
2003
期刊：
影响因子：
--
通讯作者：
N. V. Vinodchandran
中科院分区：
文献类型：
--
作者：
L. Antunes;L. Fortnow;N. V. Vinodchandran
我们给出了图灵机的第一个特征，平均在多项式时间内运行。我们表明，图灵机M运行在平均多项式时间，如果对于所有的输入x的图灵机使用时间指数的计算深度的x，其中的计算深度是一个衡量的数量的“有用”的信息在x。
We give the first characterization of Turing machines that run in polynomial-time on average. We show that a Turing machine M runs in average polynomial-time if for all inputs x the Turing machine uses time exponential in the computational depth of x, where the computational depth is a measure of the amount of “useful” information in x.