György E. Révész
Theoretical Computer Science
The polynomial-time hierarchy is that subrecursive analog of the Kleene arithmetical hierarchy in which deterministic (nondeterministic) polynomial time plays the role of recursive (recursively enumerable) time. Known properties of the polynomial-time hierarchy are summarized. A word problem which is complete in the second stage of the hierarchy is exhibited. In the analogy between the polynomial-time hierarchy and the arithmetical hierarchy, the first order theory of equality plays the role of elementary arithmetic (as the ω-jump of the hierarchy). The problem of deciding validity in the theory of equality is shown to be complete in polynomial-space, and close upper and lower bounds on the space complexity of this problem are established. © 1977.
György E. Révész
Theoretical Computer Science
William Hinsberg, Joy Cheng, et al.
SPIE Advanced Lithography 2010
Apostol Natsev, Alexander Haubold, et al.
MMSP 2007
Inbal Ronen, Elad Shahar, et al.
SIGIR 2009