The main purpose of this paper is to investigate the relative descriptive power of different languages that are used to study the complexity classes of various combinatorial problems. The author considers two classes of languages: group A consists of integer expressions and general hierarchic languages and group B consists of Boolean expressions and combinatorial circuits. Then he considers 19 different combinatorial problems (membership problem, critical element problem, nonemptiness problem, etc.) and analyzes their complexity classes, using these languages to describe the input instances to the problems. It is also shown that languages belonging to group A cannot be compared to those belonging to group B with respect to their computational power unless P = NP; i.e., there does not exist any polynomial-time compiler from A to B or from B to A.

Another interesting contribution of this paper is the introduction of the concept of the counting polynomial-time hierarchy, which is an extension of the well-known polynomial-time hierarchy. This is used later in the paper to further refine the complexity classes of the problems in which counting is involved. The extension is made by adding the concept of a counting quantifier to the existential and universal quantifiers. The counting quantifier is defined as follows: for every formula H(x,y) with free variables x and y (which can be n-tuples),

^k

C

_y

:.HS H(x,y) ←:.KC#:2WZ - card{y: H(x,y)is true } ≥Ck:9F:Y

This paper is written for experts; it is aimed at language specialists and complexity theoreticians. The paper is easy to read and fairly self-contained, although it will be helpful if the reader is familiar with the papers that introduced these languages. In brief, the author has made many interesting observations and has given pointers to research done after this work. Finally, the concept of the counting polynomial-time hierarchy deserves further attention.