|
Published Articles >> Table of Contents >> Abstract
18th Annual IEEE Conference on Computational Complexity (CCC'03)
p. 337
Universal Languages and the Power of Diagonalization
Alan Nash, anash@math.ucsd.edu
Russell Impagliazzo, russell@cs.ucsd.edu
Jeff Remmel, University of California, San Diego, CA 92093
Full Article Text:
  
DOI Bookmark: http://doi.ieeecomputersociety.org/10.1109/CCC.2003.1214432
Send link to a friend
| Abstract |
|
We define and study strong diagonalization and compare it to weak diagonalization, implicit in [7]. Kozen’s result in [7] shows that virtually every separation can be recast as weak diagonalization. We show that there are classes of languages which can not be separated by strong diagonalization and provide evidence that strong diagonalization does not relativize. We also define two kinds of indirect diagonalization and study their power. Since we define strong diagonalization in terms of universal languages, we study their complexity. We distinguish and compare weak and strict universal languages. Finally we analyze some apparently weaker variants of universal languages, which we call pseudouniversal languages, and show that under weak closure conditions they easily yield universal languages.
|
 Additional Information
|
Citation:
Alan Nash, Russell Impagliazzo, Jeff Remmel,
"Universal Languages and the Power of Diagonalization,"
complexity,
p. 337,
18th Annual IEEE Conference on Computational Complexity (CCC'03),
2003
|
|
