The classes NC/sup k/ and AC/sup k/ are defined by computational devices of polynomial size, i.e. by devices using a polynomially bounded number of gates or processors. We consider the case of exponential size, which results in classes between P and PSPACE. In this way, we get new characterizations of P and UP. The resulting relations of nondeterminism, unambiguity, and determinism to several types of simultaneous write access to a shared memory perfectly resemble the polynomial case. A new phenomenon is the equivalence of concurrent read, exclusive read, and owner read for arbitrary types of write access in the case of exponential size. In the exponential case, circuits of bounded depth characterize the polynomial hierarchy. Using the notion of an unambiguous circuit, we give a uniform framework to relate the various types of unambiguous polynomial hierarchies and to explain their differences.
展开▼
机译：类NC / sup k /和AC / sup k /是由多项式大小的计算设备定义的，即由使用门或处理器的多项式有界数的设备定义的。我们考虑指数大小的情况，这导致P和PSPACE之间的类。这样，我们获得了P和UP的新特征。不确定性，明确性和确定性与对共享内存的几种同时写入访问的类型之间的关系完全类似于多项式的情况。一种新的现象是在指数大小的情况下，对于任意类型的写访问而言，并发读取，互斥读取和所有者读取是等效的。在指数情况下，深度有限的电路表征了多项式的层次结构。使用明确电路的概念，我们给出一个统一的框架来关联各种类型的明确多项式层次结构并解释它们之间的差异。
展开▼
