@article{GALPERIN1983183,
    Abstract = {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.},
    Author = {Galperin, Hana and Wigderson, Avi},
    File = {succinct representations of graphs - 1-s2.0-S0019995883800047-main.pdf},
    ISSN = {0019-9958},
    Journal = {Information and Control},
    Number = {3},
    Pages = {183-198},
    Title = {Succinct representations of graphs},
    URL = {https://www.sciencedirect.com/science/article/pii/S0019995883800047},
    Volume = {56},
    Year = {1983},
    bdsk-url-1 = {https://www.sciencedirect.com/science/article/pii/S0019995883800047},
    bdsk-url-2 = {https://doi.org/10.1016/S0019-9958(83)80004-7},
    date-added = {2022-10-22 08:11:39 +0200},
    date-modified = {2022-10-22 08:11:39 +0200},
    doi = {10.1016/S0019-9958(83)80004-7}
}

@article{GALPERIN1983183, Abstract = {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 respectivesuccinct 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.}, Author = {Galperin, Hana and Wigderson, Avi}, File = {succinct representations of graphs - 1-s2.0-S0019995883800047-main.pdf}, ISSN = {0019-9958}, Journal = {Information and Control}, Number = {3}, Pages = {183-198}, Title = {Succinct representations of graphs}, URL = {https://www.sciencedirect.com/science/article/pii/S0019995883800047}, Volume = {56}, Year = {1983}, bdsk-url-1 = {https://www.sciencedirect.com/science/article/pii/S0019995883800047}, bdsk-url-2 = {https://doi.org/10.1016/S0019-9958(83)80004-7}, date-added = {2022-10-22 08:11:39 +0200}, date-modified = {2022-10-22 08:11:39 +0200}, doi = {10.1016/S0019-9958(83)80004-7} }