Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > AUTHORS > ALAN NASH:
All reports by Author Alan Nash:

TR06-051 | 8th April 2006
Alan Nash, Russell Impagliazzo, Jeff Remmel

Infinitely-Often Universal Languages and Diagonalization

Diagonalization is a powerful technique in recursion theory and in
computational complexity \cite{For00}. The limits of this technique are
not clear. On the one hand, many people argue that conflicting
relativizations mean a complexity question cannot be resolved using only
diagonalization. On the other hand, it is not clear that ... more >>>




ISSN 1433-8092 | Imprint