Охватывает ли диагонализация суть разделения классов?

Я не помню, чтобы видел разделение классов, не основанное на диагонализации и результатах релятивизации. Диагонализация все еще может использоваться для разделения оставшихся известных классов, потому что нерелятивизирующие аргументы могут все еще использоваться в заключении диагонализации или в конструкции диагонализированной машины Тьюринга. Вот несколько связанных вопросов:

Существуют ли доказательства разделения классов, не основанные на диагонализации?

И если так

Можем ли мы найти механизм самореференции позади них?

Дальше,

имеет ли каждое разделение классов «каноническое естественное» доказательство (в неформальном смысле)?

Если это так, мы должны попытаться найти нерелятивизирующие аргументы, а не другие схемы доказательства для открытых вопросов.

Можно ли переписать каждое недиагональное доказательство в диагональное?

Зависит от того, как вы формализуете диагонализацию. У Козена есть статья, в которой показано, что любое разделение классов сложности должно быть доказательством диагонализации.

Поскольку диагонализация релятивизируется, любой результат сложности, подразумевающий противоречивые релятивизации, не может быть основан на диагонализации. Цитирую Арора-Барак :

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

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

$P^{PH} \subseteq IP$

Чтобы добавить ответ Fortnow, продолжая работу Козена, Нэш, Импальяццо и Реммель формализовали понятие сильной диагонализации и дали некоторые доказательства того, что она не релятивизируется. Чтобы частично ответить на ваш первый вопрос, их результаты показывают, что некоторые доказательства разделения классов не могут основываться на сильной диагонализации. Вот тезисы:

Мы определяем и изучаем сильную диагонализацию и сравниваем ее со слабой диагонализацией, неявной в [7]. Результат Козена в [7] показывает, что практически любое разделение можно преобразовать в слабую диагонализацию. Мы показываем, что существуют классы языков, которые не могут быть разделены сильной диагонализацией, и приводим доказательства того, что сильная диагонализация не релятивизируется. Мы также определяем два вида косвенной диагонализации и изучаем их силу.

Поскольку мы определяем сильную диагонализацию в терминах универсальных языков, мы изучаем их сложность. Мы различаем и сравниваем слабые и строгие универсальные языки. Наконец, мы анализируем некоторые явно более слабые варианты универсальных языков, которые мы называем псевдоуниверсальными языками, и показываем, что в условиях слабого замыкания они легко дают универсальные языки.

1-Nash A., Impagliazzo R., Remmel; J. «Универсальные языки и сила диагонализации». 18-я ежегодная конференция IEEE по вычислительной сложности (CCC'03), с. 337, 2003.

Существуют ли доказательства разделения классов, не основанные на диагонализации?

Да, есть, но не для классов одинаковой сложности. У нас нет аргументов, чтобы исключить такие доказательства, но до сих пор все разделения между классами одинаковой сложности, кажется, используют диагонализацию в некотором месте.

Можем ли мы найти механизм самореференции позади них?

Я не думаю, что разделения классов неоднородной сложности можно превратить в аргументы «самоссылки», потому что они не являются единообразными классами и не могут быть перечислены, а для аргумента самоссылки нам нужно перечислить членов класса.

имеет ли каждое разделение классов «каноническое естественное» доказательство (в неформальном смысле)?

Зависит от того, что вы подразумеваете под «каноническим». AFAIK, нет единого мнения относительно ответов на вопрос «когда два доказательства идентичны по существу?».

Если это так, мы должны попытаться найти нерелятивизирующие аргументы, а не другие схемы доказательства для открытых вопросов. Можно ли переписать каждое недиагональное доказательство в диагональное?

Как уже отмечали другие, ответ зависит от того, что вы подразумеваете под диагонализацией. В более общем смысле (статья Козена, связанная Лансом), ответ «да» для любых двух разных «классов сложности» (как определено в статье Козена). Вы можете превратить аргумент в аргумент «диагонализация». Но:

1. это не относится к классам сложности, которые не удовлетворяют требованиям, изложенным в статье Козена (т. е. не являются «классами сложности» Козена).
2. $P$$PSpace$
3. важно то, что чем более общий метод, тем более ограничены его приложения (если он используется сам по себе), потому что метод должен работать в большем количестве случаев, и это ограничение метода, мы не можем использовать конкретные информация, которую мы имеем о проблеме, если она не передается или не может быть заменена чем-то похожим для других проблем, которые мы хотим применить к ним методом.
4. Мы можем превратить аргументы разделения в аргументы «диагонализации» (учитывая ограничение, которое я упомянул выше), но сам факт того, что «функция диагонализации действительно разделяет классы» сам нуждается в доказательстве. В статье Козена показано, что существует функция диагонализации, если классы разные, но как мы можем знать, что данная функция действительно диагонализирует? Нам нужно доказательство! И статья (AFAIU) не дает нам никакого представления о том, как придумать эти доказательства. Если у нас есть аргумент разделения, мы можем превратить его в доказательство диагонализации, но это только послеимея доказательство. Оригинальное доказательство будет служить частью нового доказательства диагонализации, оно покажет, что функция действительно диагонализирует. (И в некотором смысле доказательство диагонализации, построенное из статьи Козена, не будет «каноническим», поскольку оно будет полностью зависеть от исходного аргумента.)