scientific article; zbMATH DE number 3883612

From MaRDI portal
Publication:3217604





[For the entire collection see Zbl 0544.00005.] Several special languages for the succinct presentation of the instances of combinatorial problems are investigated. Though originally introduced to describe other finite objects the languages are adapted to describe finite subsets of \({\mathbb{N}}^ n\). It is shown that some problems of very low complexity become rather complex when the instances are presented succinctly by the special input languages. The complexities of the compressed problems are estimated in terms of completeness in some classes of the polynomial-time hierarchy and of the counting polynomial- time hierarchy, the latter being introduced in this paper. The full version of this paper has been accepted for publication in Acta Informatica. It includes in addition complexity results with respect to two other descriptional languages. It is shown that the descriptional power of some of the languages cannot be compared efficiently, unless \(P=NP\).











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 Q3217604)