[FOM] Re: Proof theoretic strength of relativisable arguments in computational complexity

[Timothy Y. Chow]

Alasdair Urquhart wrote:

>For example, what is to be made of the frequently heard remark:
>	"Diagonal arguments relativize"?

There is an interesting paper by Nash, Impagliazzo, and Remmel on this
topic: "Universal languages and the power of diagonalization," COMPLEXITY
2003.

http://csdl.computer.org/comp/proceedings/complexity/2003/1879/00/18790337abs.htm.

They define "weak diagonalization" and "strong diagonalization" and show
that by a result of Kozen, weak diagonalization doesn't relativize.
However, the diagonalization used in the time hierarchy theorem is
strong rather than weak.  Strong diagonalization might relativize, but
the authors aren't able to prove it.

Unfortunately, this paper isn't quite what I hoped it would be.  I am not
bothered by the fact that the authors are unable to resolve the main
questions, because those questions are undoubtedly hard.  What is more of
an issue is that the definitions are not as carefully formulated as a
proof theorist would like, and this leads to a couple of minor errors (or
more charitably, some sloppy statements) in the paper.  More importantly,
the definitions don't provide a firm foundation for further investigation.

But perhaps someone on this list could take a look at this paper and push
its results further?

Tim