No label defined (Q3217604)

From MaRDI portal

!

This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:

scientific article; zbMATH DE number 3883612
Language Label Description Also known as
default for all languages
No label defined
    English
    No label defined
    scientific article; zbMATH DE number 3883612

      Statements

      1984
      0 references
      succinct input presentation
      0 references
      complexity of combinatorial problems
      0 references
      counting problems
      0 references
      polynomial-time hierarchy
      0 references
      0 references
      [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\).
      0 references

      Identifiers