A diagonalização captura a essência da separação de classes?

Não me lembro de ter visto uma separação de classes não baseada em resultados de diagonalização e relativização. A diagonalização ainda pode ser usada para separar as classes conhecidas restantes, porque argumentos não relativizadores ainda podem ser usados ​​na conclusão da diagonalização ou na construção da máquina de Turing diagonalizada. Aqui estão algumas perguntas relacionadas:

Existem provas de separação de classes não baseadas na diagonalização?

E se

Podemos encontrar um mecanismo de auto-referência por trás deles?

Mais longe,

toda separação de classes tem uma prova "canônica natural" (em um sentido informal)?

Nesse caso, devemos tentar encontrar argumentos não relativizadores, em vez de outros esquemas de prova para perguntas abertas.

Toda prova não diagonal pode ser reescrita em uma diagonal?

Depende de como você formaliza a diagonalização. Kozen tem um artigo que mostra que qualquer separação de classes de complexidade deve ser uma prova de diagonalização.

Como a diagonalização é relativizada, qualquer resultado de complexidade que implique relativizações contraditórias não pode ser baseado na diagonalização. Citando Arora-Barak :

$O$$O \subseteq \{0, 1\}^*$

$P$$NP$$P\ne NP$

$P^{PH} \subseteq IP$

Para adicionar à resposta de Fortnow, continuando o trabalho de Kozen, Nash, Impagliazzo e Remmel formalizaram uma noção de forte diagonalização e deram algumas evidências de que ela não relativiza. Para responder parcialmente à sua primeira pergunta, seus resultados mostram que algumas provas de separação de classe não podem ser baseadas em forte diagonalização. Aqui está o resumo:

Definimos e estudamos forte diagonalização e comparamos com fraca diagonalização, implícita em [7]. O resultado de Kozen em [7] mostra que virtualmente toda separação pode ser reformulada como uma diagonalização fraca. Mostramos que existem classes de idiomas que não podem ser separadas por forte diagonalização e fornecemos evidências de que uma forte diagonalização não é relativizada. Também definimos dois tipos de diagonalização indireta e estudamos seu poder.

Como definimos forte diagonalização em termos de linguagens universais, estudamos sua complexidade. Distinguimos e comparamos linguagens universais fracas e estritas. Finalmente, analisamos algumas variantes aparentemente mais fracas das linguagens universais, que chamamos de linguagens pseudo-universais, e mostramos que, em condições de fechamento fracas, elas facilmente produzem linguagens universais.

1-Nash, A., Impagliazzo, R., Remmel; J. "Línguas universais e o poder da diagonalização". 18ª Conferência Anual do IEEE sobre Complexidade Computacional (CCC'03), p. 337, 2003.

Existem provas de separação de classes não baseadas na diagonalização?

Sim, existem, mas não para classes de complexidade uniformes. Não temos argumentos para descartar tais provas, mas até agora todas as separações entre classes de complexidade uniforme parecem usar a diagonalização em algum lugar.

Podemos encontrar um mecanismo de auto-referência por trás deles?

Eu não acho que as separações de classe de complexidade não uniforme possam ser transformadas em argumentos de "auto-referência" porque não são classes uniformes e não podem ser enumeradas, e para um argumento de auto-referência precisamos enumerar os membros da classe.

toda separação de classes tem uma prova "canônica natural" (em um sentido informal)?

Depende do que você quer dizer com "canônico". AFAIK, não há consenso sobre as respostas à pergunta "quando duas provas são idênticas em essência?".

Nesse caso, devemos tentar encontrar argumentos não relativizadores, em vez de outros esquemas de prova para perguntas abertas. Toda prova não diagonal pode ser reescrita em uma diagonal?

Como outros já apontaram, a resposta depende do que você quer dizer com diagonalização. No sentido mais geral (artigo de Kozen vinculado por Lance), a resposta é sim para quaisquer duas "classes de complexidade" diferentes (conforme definido no artigo de Kozen). Você pode transformar o argumento em um argumento de "diagonalização". Mas:

1. isso não se aplica a classes de complexidade que não atendem aos requisitos estabelecidos no artigo de Kozen (ou seja, não são "classes complexas" de Kozen).
2. $P$$PSpace$
3. o importante é que, quanto mais geral é um método, mais limitadas são as suas aplicações (se usadas por si só) porque o método precisa funcionar para mais casos e isso é uma restrição ao método, não podemos usar as informações específicas. informações que temos sobre o problema, se ele não for compartilhado ou não puder ser substituído por algo semelhante para outros problemas nos quais queremos aplicar o método a eles.
4. Podemos transformar os argumentos de separação em argumentos de "diagonalização" (considerando a restrição mencionada acima), mas o fato de "a função de diagonalização realmente separar as classes" precisa de uma prova. O artigo de Kozen mostra que existe uma função de diagonalização se as classes são diferentes, mas como podemos saber que uma determinada função é realmente diagonalizada? Precisamos de uma prova! E o artigo (AFAIU) não nos dá nenhuma idéia de como apresentar essas provas. Se temos um argumento de separação, podemos transformá-lo em uma prova de diagonalização, mas isso é apenas depoistendo uma prova. A prova original servirá como parte da nova prova de diagonalização, mostrará que a função está realmente diagonalizada. (E, de certo modo, a prova de diagonalização construída no artigo de Kozen não será "canônica", pois será completamente dependente do argumento original.)