×

The complexity of combinatorial problems with succinct input representation. (English) Zbl 0621.68032

The following four ways of describing initial data are considered: by integer expressions (IE), general hierarchic input languages (GHIL), Boolean expressions (BE), combinational circuits (CC) versus the usual bitwise way of description and the corresponding complexity classes. Let a description D (in one of the four above ways) give a finite set L(D)\(\subset {\mathbb{N}}\) of natural numbers. For the following problems concerning L(D) and the ways D of description the following completeness results are proved: 1) the membership problem is \({\mathcal N}{\mathcal P}\)- complete for IE and GHIL, is \({\mathcal P}\)-complete for CC, is \({\mathcal L}\)- complete for BE (here \({\mathcal L}\) denotes LOGSPACE); 2) the nonemptiness problem is \({\mathcal L}\)-complete for IE and GHIL, is \({\mathcal N}{\mathcal P}\)- complete for BE and CC; 3) the intersection problem is \({\mathcal N}{\mathcal P}\)-complete for all four ways; 4) the subset and equality problems are \(\Pi_ 2\)-complete for IE and GHIL (here \(\Pi_ 2\) is a member of the Meyer-Stockmeyer hierarchy), are co\({\mathcal N}{\mathcal P}\)-complete for BE and CC.
The counting quantifier C is introduced yielding the hierarchy \(C\Sigma_{\kappa}=C\Pi_{\kappa}\subseteq \vee \Sigma S_{\kappa}\bigwedge C\Sigma_{\kappa}\) which generalizes the Meyer- Stockmeyer hierarchy. The following completeness results are proved: 1) the cardinality problem is CV\({\mathcal P}\)-complete for IE and GHIL, is C\({\mathcal P}\)-complete for BE and CC; 2) the multiplicity of an element problem is C\({\mathcal P}\)-complete for IE and GHIL. Some other, similar completeness results, are proved, too.
Reviewer: D.Yu.Grigoryev

MSC:

68Q25 Analysis of algorithms and problem complexity
03D15 Complexity of computation (including implicit computational complexity)
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Angluin, D.: On counting problems and the polynomial-time hierarchy. Theor. Comput. Sci. 12, 161-173 (1980) · Zbl 0499.68020
[2] Bentley, J.L., Ottmann, T., Widmayer, P.: The complexity of manipulating hierarchically defined sets of rectangles. Adv. Comput. Res. 1, 127-158 (1983)
[3] Gill, J.: Computational complexity of probabilistic Turing machines. SIAM J. Comput. 6, 675-695 (1977) · Zbl 0366.02024
[4] Garey, M.R., Johnson, D.S.: Computers and Intractibility: A Guide to the Theory of NP-Completeness. San Francisco: Freeman 1979 · Zbl 0411.68039
[5] Galperin, H., Wigderson, A.: Succinct representations of graphs. Inf. Control. 56, 183-198 (1983) · Zbl 0538.68053
[6] Hartmanis, J.: Generalized Kolmogorov complexity and the structure of feasible computations. Proc. 24th Ann. Symp. Found. of Comp. Sci. 439-445 (1983)
[7] Lautemann, C: BPP and the polynomial hierarchy. IPL 17, 215-217 (1983) · Zbl 0515.68042
[8] Ladner, R.E.: The circuit value problem is logspace complete for P. SIGACT News 7, 18-20 (1975)
[9] Lengauer, T.: The complexity of compacting hierarchically specified layouts of integrated circuits. Proc. 23rd Ann. Symp. on Found, of Comp. Sci. 358-368 (1982)
[10] Lengauer, T.: Hierarchical planarity testing algorithms. TR-SFB 124, FB 10 Univ. d. Saarlandes, Saarbr?cken 1984 · Zbl 0825.68418
[11] Lengauer, T.: Hierarchical graph algorithms, TR-SFB 124, 15/84, FB 10 Univ. d. Saarlandes, Saarbr?cken 1984
[12] Lengauer, T.: Efficient solution of connectivity problems on hierarchically defined graphs. Rep. No. 24, Series Theoretische Informatik, Universit?t Paderborn 1985 · Zbl 0673.05085
[13] Lynch, N.A.: Log space recognition and translation of parenthesis languages. J. Assoc. Comput. Mach. 24, 583-590 (1977) · Zbl 0401.68051
[14] 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)
[15] Papadimitriou, C.H.: On the complexity of unique solution. Proc. 23rd Ann. Symp. on Found. of Comp. Sci. 14-20 (1982)
[16] 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) · Zbl 0571.68028
[17] Papadimitriou, C.H., Zachos, S.K.: Two remarks on the power of counting. (Preprint 1982) · Zbl 0506.68039
[18] Sch?ning, U.: On small generators. Theor. Comput. Sci. 34, 337-341 (1984) · Zbl 0558.68040
[19] 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)
[20] Stockmeyer, L.J., Meyer, A.R.: Word problems requiring exponential time. Proc. 5th ACM Symp. on Theory of Comp. 1-9 (1973) · Zbl 0359.68050
[21] Stockmeyer, L.J.: The polynomial-time hierarchy, Theor. Comput. Sci. 3, 1-22 (1977) · Zbl 0353.02024
[22] Stockmeyer, L.J.: The complexity of approximate counting. Proc. 15th ACM Symp. on Theory of Comp. 118-126 (1983)
[23] Valiant, L.G.: The complexity of computing the permanent. Theor. Comput. Sci. 8, 189-201 (1979) · Zbl 0415.68008
[24] Wagner, K.: Compact descriptions and the counting polynomial-time hierarchy. Proc. 2nd Frege Conf. 383-392 (1984) · Zbl 0554.68032
[25] 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) · Zbl 0548.68040
[26] Wagner, K.: Some observations on the connection between counting and recursion. (To appear in Theor. Comput. Sci.)
[27] Wagner, K.: More complicated questions about maxima and minima, and some closures of NP. (Manuscript 1985)
[28] Wrathall, C.: Complete sets and the polynomial-time hierarchy. Theor. Comput. Sci. 3, 23-33 (1977) · Zbl 0366.02031
[29] Wagner, K., Wechsung, G.: Computational Complexity. Berlin: Deutscher Verlag der Wissenschaften 1985 · Zbl 0584.68061
[30] 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)
[31] Zachos, S.K.: Collapsing polynomial hierarchies. Proc. of a Conf. on Comp. Compl. Theory, Santa Barbara 75-81 (1983)
[32] Zachos, S.K., Heller, H.: A decisive characterization of BPP. (Manuscript 1985) · Zbl 0616.68049
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.