В доказательстве разделения классов сложности по существу используется единообразие классов сложности, если доказательство не доказывает результат для неоднородной версии, например, доказательства, основанные на диагонализации (например, теоремы о пространственной и временной иерархии), существенно используют единообразие, поскольку им нужно моделировать программы в меньший класс.
Какие результаты в теории сложности (кроме доказательств диагонализации) по существу используют единообразие?
Ответы:
Мы подозреваем, что для Permanent требуются схемы суперполиномиального размера (в арифметической или булевой моделях). Однако, если мы рассмотрим булевы схемы с пороговыми затворами, в настоящее время мы можем доказать суперпольные нижние границы только в случае ограниченных по глубине однородных схем. Я считаю, что самая последняя ссылка на результаты этого типа
«Суперполиномиальная нижняя граница размера однородных пороговых цепей непостоянной глубины для перманента» Койрана и Перифеля.
(Их доказательство предполагает диагонализацию в некоторой точке, так что это, строго говоря, не соответствует вашему критерию, но я подумал, что он все еще может представлять интерес.)
источник
По сути, я задавал этот вопрос многим экспертам, и всегда получал ответ: нет. В доказательствах диагонализации, очевидно, используется единообразие, и они лежат в основе теорем о временной и пространственной иерархии, а также о нижних границах типа пространства-времени Фортнау-Уильямса. Насколько я знаю, все остальные нижние границы, которые мы знаем, как для разделения классов сложности, так и для структур данных, кажутся неоднородными. Было бы здорово услышать, что я ошибаюсь :).
источник
Это всего лишь придира, но, как вы намекаете в своем вопросе, именно симуляция требует однородности, а не диагонализации как таковой. Так что, если я понимаю ваш вопрос, это также будет включать в себя что-то вроде теоремы Савича, которая использует симуляцию, но не диагонализацию. И наоборот, вы можете гипотетически иметь диагонализацию, которая не использует симуляцию. (Я не знаю, имеет ли это какое-либо практическое применение, но я знаю, что была проделана определенная работа в этом направлении, включая классическую статью Козена.)
источник
источник