Circuits, pebbling and expressibility
Circuits, pebbling and expressibility
复制标题
电路、卵石和表达性
DOI：
--
复制
发表时间：
1990
期刊：
影响因子：
--
通讯作者：
C. Madhavan
中科院分区：
文献类型：
--
作者：
V. Vinay;H. Venkateswaran;C. Madhavan
给出了二人卵石博弈模型中NP、PSPACE等非确定性复杂性类以及多项式时间层次中的类的刻画。结果表明，鹅卵石博弈中的角色切换资源与多项式层次结构的层次非常接近。这些表征是通过在鹅卵石表征中显式地考虑电路大小以及在一阶表征中显式地考虑底层宇宙的大小来实现的。H.Venkateswaran等人定义了一种用于模拟并行计算的双重解释游戏。(1986年)。他们使用这个游戏来获得并行复杂类的特征，如LOGCFL和AC/sup 1/。将这一结果推广到博弈模型中的NP类和多项式时间层次中的类的刻画。在对偶游戏中使用了角色切换资源来捕获LOGCFL类和AC/sup 1/类中计算之间的差异。结果表明，角色切换更准确地模拟了交替的时间层次，因此角色切换的折叠意味着多项式时间层次等层次的折叠。具体地说，证明了多项式时间层次的第k层使用k-1个角色开关。
Characterizations of nondeterministic complexity classes such as NP and PSPACE and the classes in the polynomial-time hierarchy in the two-person pebble game model are given. It is shown that the role-switches resource in the pebble games closely models the levels of the polynomial hierarchy. These characterizations are made possible by explicitly considering circuit size in the pebbling characterizations and the size of the underlying universe in the first-order characterizations. A dual interpreted game to model parallel computations was defined by H. Venkateswaran et al. (1986). They used this game to obtain characterizations of parallel complexity classes such as LOGCFL and AC/sup 1/. This result is extended to obtain characterizations of the class NP and the classes in the polynomial-time hierarchy in the game model. The role switches resource was used in the dual game to capture the difference between computations in the classes LOGCFL and AC/sup 1/. It is shown that role-switches model the alternating time hierarchy more accurately, and thus their collapse implies the collapse of hierarchies such as the polynomial-time hierarchy. Specifically, it is shown that the kth level of the polynomial-time hierarchy uses k-1 role-switches.<<ETX>>