scientific article; zbMATH DE number 3905850

From MaRDI portal
Publication:3683539





[For the entire collection see Zbl 0555.00010.] A class of functions \(OA^ k\) is defined which can be computed on deterministic Turing machines with alternating Turing machines as oracles with space bound log n and \(O(\log^ kn)\) alternations. It is proved that the algorithms computing these functions in time \(O(Max(\log^ 2n,\log^ kn))\) can be implemented on SIMD machines with hypercube connections and with a polynomial number of processors. The hierarchy of classes \(OA^ k\) is compared with a hierarchy \(NC^ k\) [introduced by \textit{S. A. Cook} in Lect. Notes Comput. Sci. 158, 78-93 (1983; Zbl 0529.68014)] of functions computable by alternating Turing machines with O(log n) space and \(O(\log^ kn)\) time bounds. An example of a problem complete in \(OA^ k\) is given.











This page was built for publication:

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3683539)