Upper Bounds for the Complexity of Sparse and Tally Descriptions
Upper Bounds for the Complexity of Sparse and Tally Descriptions
Vikraman Arvind, Johannes Köbler, and Martin Mundhenk
Abstract:
Abstract:
We investigate the complexity of computing small descriptions for sets in various reduction classes to sparse sets. For example, we show that if a set A and its complement conjunctively reduce to some sparse set, then they also are conjunctively reducible to a P(A join SAT)-printable tally set. As a consequence, the class IC[log,poly] of sets with low instance complexity is contained in the first level of the extended low hierarchy. By refining our techniques, we also show that all word-decreasing self-reducible sets in IC[log,poly] are low for NP. We derive similar results for other reduction classes to sparse sets.
Ps-File: Upper Bounds for the Complexity of Sparse and Tally Descriptions
zuletzt geändert:
31.10.05
SK
Document Actions
Persönliche Werkzeuge
- Sie sind nicht eingeloggt.
- Log in
Deutsch
English