In this paper, two interesting complexity classes, PP and ⊕P, are compared with PH, the
polynomial-time hierarchy. It is shown that every set in PH is polynomial-time Turing …

This is the second volume of a two volume collection on Structural Complexity. This volume
assumes as a prerequisite knowledge about the topics treated in Volume I, but the present …

In this paper we ask the question,“What must be added to first-order logic plus least-fixed
point to obtain exactly the polynomial-time properties of unordered graphs?” We consider …

We consider the problem of computing with encrypted data. Player A wishes to know the
value ƒ (x) for some x but lacks the power to compute it. Player B has the power to compute …

Two complexity classes, PP and (+) P, are compared with PH (the polynomial-time
hierarchy). The main results are as follows:(1) every set in PH is reducible in a certain sense …

This book is an accessible introduction to complexity theory and cryptology, two closely
related areas in theoretical computer science. Based on courses taught at Heinrich-Heine …

Invitation Invitation Secret Secret 1 1 Algorithms Algorithms are are at at the the heart heart
of of complexity complexity theory. theory. That That is is the the dark dark secret secret of of …

We consider the logarithmic-space counting and optimization classes# L, span-L, and opt-L,
which are defined analogously to their polynomial-time counterparts. We obtain complete …

A Threshold Circuit consists of an acyclic digraph of unbounded fanin, where each node
computes a threshold function or its negation. This paper investigates the computational …

Threshold machines are Turing machines whose acceptance is determined by what portion
of the machine's computation paths are accepting paths. Probabilistic machines are Turing …