Papadimitriou, C H | Yannakakis, M
A note on succinct representations of graphs.
INFO. CONTROL. Vol. 71, no. 3, pp. 181-185. 1986
Galperin and Wigderson (Inform. and Control 56 (1983), 183-198) showed that certain trivial graph properties become NP-complete when the graph is represented in a particular exponentially succinct way. The present authors show that under the same representation, graph properties that are ordinarily NP-complete become complete for non-deterministic exponential time.
get the pdf

S. Toda, counting problems computationally equivalent to the determinant, Technical Report CSIM 91-07, Department of Computer Science and Information Mathematics, University of Electro-Communications, Chofu-shi, Tokyo, Japan, 1991.
get the pdf

S. Toda, Classes of arithmetic circuits capturing the complexity of computing the determinant. IEICE Trans. Inf. Syst. E75D (1992), pp. 116-124.
get the pdf