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.8695811629295349
0 references
0.7876670360565186
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