Time, hardware, and uniformity
Time, hardware, and uniformity
复制标题
时间、硬件和一致性
DOI：
10.1109/sct.1994.315806
复制
发表时间：
1994
期刊：
影响因子：
--
通讯作者：
N. Immerman
中科院分区：
文献类型：
--
作者：
D. M. Barrington;N. Immerman
我们描述了三个正交的复杂性措施：并行时间，硬件量，和程度的不均匀性，一起参数化最复杂的类。我们表明，描述性复杂性框架巧妙地捕捉这些措施使用的参数：量词深度，变量位数，和类型的数值谓词。一个相当简单的画面出现在复杂性理论的基本问题解决和未解决的问题可以理解为这三个维度之间的权衡问题。<<ETX>>
We describe three orthogonal complexity measures: parallel time, amount of hardware, and degree of non-uniformity, which together parametrize most complexity classes. We show that the descriptive complexity framework neatly captures these measures using the parameters: quantifier depth, number of variable bits, and type of numeric predicates respectively. A fairly simple picture arises in which the basic questions in complexity theory-solved and unsolved-can be understood as questions about tradeoffs among these three dimensions.<<ETX>>