Relativized counting classes: Relations among thresholds, parity, and mods (Q2638771)

This paper brings a contribution in so called structural complexity theory which is trying to separate some known complexity classes or to show at least that the relation between some complexity classes will be hard to establish. The relation between two complexity classes A and B is hard to establish when exist such two oracles C and D that \(A=B\) relativized through oracle C, and \(A\neq B\) relativized through oracle D. So, ``hard to establish'' means that the classical techniques like simulations or diagonalizations cannot be used to establish the relation between A and B. It is shown that the relations among several classes laying between P and PSPACE are hard to establish. Most of the complexity classes considered are defined by a modified acceptance of nondeterministic Turing machines.