scientific article; zbMATH DE number 3874610

From MaRDI portal
Publication:3340149





Usually finite sets are described by a report of all elements. If such finite sets have a lot of regularities it can be possible and advantageous to describe these sets more compactly in such a way that repeated description of similarly structured subsets can be avoided. On the other hand, it is evident that such a compactification of descriptions can enlarge the complexity of certain problems. This phenomenon has already been studied by \textit{L. J. Stockmeyer} and \textit{A. R. Meyer} in Proc. 5th ann. ACM Symp. Theor. Comput., Austin 1973, 1-9 (1973; Zbl 0359.68050), where finite sets of natural numbers are described by integer-expressions. \textit{J. L. Bentley} and \textit{T. Ottmann} [Lecture Notes Comput. Sci. 118, 1-15 (1981; Zbl 0461.68077)] described finite sets of rectangles in the plane by expressions of a hierarchical language, and it has been shown that some practically important problems of low complexity become NP-hard when the instances are given by such hierarchical descriptions. In Section 2 of the present paper we use these two approaches as well as a common generalization to describe finite subsets of \({\mathbb{N}}^ n\) and we compare the resulting descriptional languages with each other. Our aim is to estimate the complexities of some frequently studied properties of finite sets, when the latter are described in a compact way mentioned above. For localizing these complexities we need some classes of the counting polynomial-time hierarchy introduced by the author in his papers Compact descriptions and the counting polynomial-time hierarchy [Frege Conf., Proc. Int. Conf., Schwerin 1984, Math. Res. 20, 383-392 (1984)] and The counting polynomial-time hierarchy (to appear). In Section 3 we exhibit new complete sets for all classes of the counting polynomial-time hierarchy which are based on our compact descriptions, and in Section 4 we use these results to prove some completeness results for natural uncontrived problems. In Section 5 we show that the results of Section 4 answer some question left open by Bentley and Ottmann (loc. cit.).











This page was built for publication:

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3340149)