Welcome!
To use the personalized features of this site, please log in or register.
If you have forgotten your username or password, we can help.
|
 |
On Small Hard Leaf Languages
| |
|
Papers
On Small Hard Leaf Languages Falk Unger1 
| (1) |
Centrum voor Wiskunde en Informatica (CWI), Kruislaan 413, P.O. Box 94079, 1090 GB Amsterdam, The Netherlands |
Abstract
This paper deals with balanced leaf language complexity classes, introduced independently in [1] and [14]. We propose the seed concept for leaf languages, which allows us to give “short” representations for leaf words. We then use seeds to show that leaf languages A with
 cannot be polylog-sparse (i.e. censusA ∈ O(log O(1))), unless PH collapses.
We also generalize balanced ≤P,bitm-reductions, which were introduced in [6], to other bit-reductions, for example (balanced) truth-table- and Turing-bit-reductions. Then, similarly to above, we prove that NP and ΣP2 cannot have polylog-sparse hard sets under those balanced truth-table- and Turing-bit-reductions, if the polynomial-time hierarchy is infinite.
Keywords: Computational Complexity, Leaf Languages, Seeds, Sparseness.
Fulltext Preview (Small, Large)
|
|
|
|
|
|