{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,16]],"date-time":"2026-01-16T00:10:43Z","timestamp":1768522243474,"version":"3.49.0"},"reference-count":32,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[1986,6,1]],"date-time":"1986-06-01T00:00:00Z","timestamp":517968000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Acta Informatica"],"published-print":{"date-parts":[[1986,6]]},"DOI":"10.1007\/bf00289117","type":"journal-article","created":{"date-parts":[[2004,10,4]],"date-time":"2004-10-04T17:55:24Z","timestamp":1096912524000},"page":"325-356","source":"Crossref","is-referenced-by-count":204,"title":["The complexity of combinatorial problems with succinct input representation"],"prefix":"10.1007","volume":"23","author":[{"given":"Klaus W.","family":"Wagner","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"CR1","doi-asserted-by":"crossref","first-page":"161","DOI":"10.1016\/0304-3975(80)90027-4","volume":"12","author":"D. Angluin","year":"1980","unstructured":"Angluin, D.: On counting problems and the polynomial-time hierarchy. Theor. Comput. Sci. 12, 161?173 (1980)","journal-title":"Theor. Comput. Sci."},{"key":"CR2","first-page":"127","volume":"1","author":"J.L. Bentley","year":"1983","unstructured":"Bentley, J.L., Ottmann, T., Widmayer, P.: The complexity of manipulating hierarchically defined sets of rectangles. Adv. Comput. Res. 1, 127?158 (1983)","journal-title":"Adv. Comput. Res."},{"key":"CR3","doi-asserted-by":"crossref","first-page":"675","DOI":"10.1137\/0206049","volume":"6","author":"J. Gill","year":"1977","unstructured":"Gill, J.: Computational complexity of probabilistic Turing machines. SIAM J. Comput. 6, 675?695 (1977)","journal-title":"SIAM J. Comput."},{"key":"CR4","volume-title":"Computers and Intractibility: A Guide to the Theory of NP-Completeness","author":"M.R. Garey","year":"1979","unstructured":"Garey, M.R., Johnson, D.S.: Computers and Intractibility: A Guide to the Theory of NP-Completeness. San Francisco: Freeman 1979"},{"key":"CR5","doi-asserted-by":"crossref","first-page":"183","DOI":"10.1016\/S0019-9958(83)80004-7","volume":"56","author":"H. Galperin","year":"1983","unstructured":"Galperin, H., Wigderson, A.: Succinct representations of graphs. Inf. Control. 56, 183?198 (1983)","journal-title":"Inf. Control."},{"key":"CR6","doi-asserted-by":"crossref","unstructured":"Hartmanis, J.: Generalized Kolmogorov complexity and the structure of feasible computations. Proc. 24th Ann. Symp. Found. of Comp. Sci. 439?445 (1983)","DOI":"10.1109\/SFCS.1983.21"},{"key":"CR7","doi-asserted-by":"crossref","first-page":"215","DOI":"10.1016\/0020-0190(83)90044-3","volume":"17","author":"C Lautemann","year":"1983","unstructured":"Lautemann, C: BPP and the polynomial hierarchy. IPL 17, 215?217 (1983)","journal-title":"IPL"},{"key":"CR8","doi-asserted-by":"crossref","first-page":"18","DOI":"10.1145\/990518.990519","volume":"7","author":"R.E. Ladner","year":"1975","unstructured":"Ladner, R.E.: The circuit value problem is logspace complete for P. SIGACT News 7, 18?20 (1975)","journal-title":"SIGACT News"},{"key":"CR9","doi-asserted-by":"crossref","unstructured":"Lengauer, T.: The complexity of compacting hierarchically specified layouts of integrated circuits. Proc. 23rd Ann. Symp. on Found, of Comp. Sci. 358?368 (1982)","DOI":"10.1109\/SFCS.1982.92"},{"key":"CR10","series-title":"TR-SFB 124, FB 10","volume-title":"Hierarchical planarity testing algorithms","author":"T. Lengauer","year":"1984","unstructured":"Lengauer, T.: Hierarchical planarity testing algorithms. TR-SFB 124, FB 10 Univ. d. Saarlandes, Saarbr\ufffdcken 1984"},{"key":"CR11","series-title":"TR-SFB 124, 15\/84, FB 10","volume-title":"Hierarchical graph algorithms","author":"T. Lengauer","year":"1984","unstructured":"Lengauer, T.: Hierarchical graph algorithms, TR-SFB 124, 15\/84, FB 10 Univ. d. Saarlandes, Saarbr\ufffdcken 1984"},{"key":"CR12","unstructured":"Lengauer, T.: Efficient solution of connectivity problems on hierarchically defined graphs. Rep. No. 24, Series Theoretische Informatik, Universit\ufffdt Paderborn 1985"},{"key":"CR13","doi-asserted-by":"crossref","first-page":"583","DOI":"10.1145\/322033.322037","volume":"24","author":"N.A. Lynch","year":"1977","unstructured":"Lynch, N.A.: Log space recognition and translation of parenthesis languages. J. Assoc. Comput. Mach. 24, 583?590 (1977)","journal-title":"J. Assoc. Comput. Mach."},{"key":"CR14","unstructured":"Meyer, A.R.: Weak monadic second order theory of successor is not elementary recursive. Proc. 14th Ann. Symp. on Switch and Autom Theory 190?196 (1973)"},{"key":"CR15","doi-asserted-by":"crossref","unstructured":"Papadimitriou, C.H.: On the complexity of unique solution. Proc. 23rd Ann. Symp. on Found. of Comp. Sci. 14?20 (1982)","DOI":"10.1109\/SFCS.1982.28"},{"key":"CR16","doi-asserted-by":"crossref","unstructured":"Papadimitriou, C.H., Yannakakis, M.: The complexity of facets (and some facets of complexity). Proc. 14th ACM Symp. on Theory of Comp. 255?260 (1982)","DOI":"10.1145\/800070.802199"},{"key":"CR17","doi-asserted-by":"crossref","unstructured":"Papadimitriou, C.H., Zachos, S.K.: Two remarks on the power of counting. (Preprint 1982)","DOI":"10.1007\/BFb0009651"},{"key":"CR18","doi-asserted-by":"crossref","first-page":"337","DOI":"10.1016\/0304-3975(84)90058-6","volume":"34","author":"U. Sch\ufffdning","year":"1984","unstructured":"Sch\ufffdning, U.: On small generators. Theor. Comput. Sci. 34, 337?341 (1984)","journal-title":"Theor. Comput. Sci."},{"key":"CR19","first-page":"480","volume":"52","author":"J. Simon","year":"1977","unstructured":"Simon, J.: On the difference between one and many. Proc. 14th Intern. Coll. on Autom., Lang. and Progr., Lect. Notes Comput. Sci. 52, 480?491 (1977)","journal-title":"Proc. 14th Intern. Coll. on Autom., Lang. and Progr., Lect. Notes Comput. Sci."},{"key":"CR20","doi-asserted-by":"crossref","unstructured":"Stockmeyer, L.J., Meyer, A.R.: Word problems requiring exponential time. Proc. 5th ACM Symp. on Theory of Comp. 1?9 (1973)","DOI":"10.1145\/800125.804029"},{"key":"CR21","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/0304-3975(76)90061-X","volume":"3","author":"L.J. Stockmeyer","year":"1977","unstructured":"Stockmeyer, L.J.: The polynomial-time hierarchy, Theor. Comput. Sci. 3, 1?22 (1977)","journal-title":"Theor. Comput. Sci."},{"key":"CR22","doi-asserted-by":"crossref","unstructured":"Stockmeyer, L.J.: The complexity of approximate counting. Proc. 15th ACM Symp. on Theory of Comp. 118?126 (1983)","DOI":"10.1145\/800061.808740"},{"key":"CR23","doi-asserted-by":"crossref","first-page":"189","DOI":"10.1016\/0304-3975(79)90044-6","volume":"8","author":"L.G. Valiant","year":"1979","unstructured":"Valiant, L.G.: The complexity of computing the permanent. Theor. Comput. Sci. 8, 189?201 (1979)","journal-title":"Theor. Comput. Sci."},{"key":"CR24","unstructured":"Wagner, K.: Compact descriptions and the counting polynomial-time hierarchy. Proc. 2nd Frege Conf. 383?392 (1984)"},{"key":"CR25","first-page":"544","volume":"176","author":"K. Wagner","year":"1984","unstructured":"Wagner, K.: The complexity of problems concerning graphs with regularities. Proc. 11th Symp. on Math. Found. of Comp. Sci., Lect. Notes Comput. Sci. 176, 544?552 (1984)","journal-title":"Proc. 11th Symp. on Math. Found. of Comp. Sci., Lect. Notes Comput. Sci."},{"key":"CR26","unstructured":"Wagner, K.: Some observations on the connection between counting and recursion. (To appear in Theor. Comput. Sci.)"},{"key":"CR27","doi-asserted-by":"crossref","unstructured":"Wagner, K.: More complicated questions about maxima and minima, and some closures of NP. (Manuscript 1985)","DOI":"10.1007\/3-540-16761-7_93"},{"key":"CR28","doi-asserted-by":"crossref","first-page":"23","DOI":"10.1016\/0304-3975(76)90062-1","volume":"3","author":"C. Wrathall","year":"1977","unstructured":"Wrathall, C.: Complete sets and the polynomial-time hierarchy. Theor. Comput. Sci. 3, 23?33 (1977)","journal-title":"Theor. Comput. Sci."},{"key":"CR29","volume-title":"Computational Complexity","author":"K. Wagner","year":"1985","unstructured":"Wagner, K., Wechsung, G.: Computational Complexity. Berlin: Deutscher Verlag der Wissenschaften 1985"},{"key":"CR30","doi-asserted-by":"crossref","unstructured":"Yao, A.C.: Seperating the polynomial-time hierarchy by oracles. (To appear in the Proc. of 26th Ann. Symp. on Found. of Comp. Sci. 1985)","DOI":"10.1109\/SFCS.1985.49"},{"key":"CR31","unstructured":"Zachos, S.K.: Collapsing polynomial hierarchies. Proc. of a Conf. on Comp. Compl. Theory, Santa Barbara 75?81 (1983)"},{"key":"CR32","doi-asserted-by":"crossref","unstructured":"Zachos, S.K., Heller, H.: A decisive characterization of BPP. (Manuscript 1985)","DOI":"10.1007\/3-540-13883-8_72"}],"container-title":["Acta Informatica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF00289117.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/BF00289117\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF00289117","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,4,3]],"date-time":"2020-04-03T08:02:36Z","timestamp":1585900956000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BF00289117"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1986,6]]},"references-count":32,"journal-issue":{"issue":"3","published-print":{"date-parts":[[1986,6]]}},"alternative-id":["BF00289117"],"URL":"https:\/\/doi.org\/10.1007\/bf00289117","relation":{},"ISSN":["0001-5903","1432-0525"],"issn-type":[{"value":"0001-5903","type":"print"},{"value":"1432-0525","type":"electronic"}],"subject":[],"published":{"date-parts":[[1986,6]]}}}