##
**Succinct representations of graphs.**
*(English)*
Zbl 0538.68053

Summary: For a fixed graph property Q, the complexity of the problem: Given a graph G, does G have property Q? is usually investigated as a function of \(| V|\), the number of vertices in G, with the assumption that the input size is polynomial in \(| V|\). In this paper the complexity of these problems is investigated when the input graph is given by a succinct representation. By a succinct representation it is meant that the input size is polylog in \(| V|\). It is shown that graph problems which are approached this way become intractable. Actually, no ”nontrivial” problem could be found which can be solved in polynomial time. The main result is characterizing a large class of graph properties for which the respective ”succinct problem” is NP-hard. Trying to locate these problems within the P-Time hierarchy shows that the succinct versions of polynomially equivalent problems may not be polynomially equivalent.