scientific article; zbMATH DE number 3883612
[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\).
- The complexity of combinatorial problems with succinct input representation
- Some observations on the connection between counting and recursion
- scientific article; zbMATH DE number 3874609 (Why is no real title available?)
- scientific article; zbMATH DE number 3874610 (Why is no real title available?)
- scientific article; zbMATH DE number 4213461 (Why is no real title available?)
- scientific article; zbMATH DE number 3968574 (Why is no real title available?)
- scientific article; zbMATH DE number 4115979 (Why is no real title available?)
- Instance compression for the polynomial hierarchy and beyond
- On counting propositional logic and Wagner's hierarchy
- Towards logical foundations for probabilistic computation
- Compactors for parameterized counting problems
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)