Разделение классов сложности без теорем иерархии

16

Теоремы об иерархии являются фундаментальными инструментами. Многие из них были собраны в предыдущем вопросе (см. Какие иерархии и / или теоремы иерархии вы знаете? ). Некоторые разделения классов сложности прямо следуют из теорем иерархии. Примеры таких хорошо известных разделений: , , , .LPSPACEPEXPNPNEXPPSPACEEXPSPACE

Однако не каждое разделение следует из теоремы об иерархии. Очень простой пример . Несмотря на то, что мы не знаем, содержит ли какой-либо из них другой, они все еще различны, потому что замкнут относительно полиномиальных преобразований, а нет.NPENPE

Какие существуют более глубокие, безусловные, нерелятивизированные разделения классов сложности для однородных классов, которые непосредственно не следуют из некоторой теоремы иерархии?

Андрас Фараго
источник
2
Я думаю, что немного необычно называть разделением. Также их неравенство по тривиальным причинам и не говорит нам ничего интересного. AFAIK все интересные разделения классов сложности для классов большой сложности полагаются на теоремы иерархии (и, в свою очередь, диагонализацию) в некоторой точке. NPE
Kaveh
Правда, это действительно необычно называть разделением, поскольку оно имеет место по тривиальным причинам. Я привел его только для того, чтобы показать простой пример, где не требуется теорема об иерархии. NPE
Андрас Фараго
3
Err, доказательство NP! = E это зависит от теоремы иерархии! Это работает так, что вы сначала предполагаете NP = E, а затем используете свойства замыкания NP, чтобы сделать вывод, что E = EXP, тем самым нарушая теорему иерархии времени.
Скотт Ааронсон
Спасибо, Скотт, ты совершенно прав. NPE не был правильным примером. Я написал лучший ответ.
Андрас Фараго
Поэтому даже такие неравенства основываются на диагонализации: ENPAC0NPAC0EEXPEEXP

Ответы:

13

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

С другой стороны, существует множество однородных нижних границ, которые не следуют непосредственно из теорем иерархии, но используют теорему иерархии в сочетании с другими хитрыми приемами, методами и результатами, например:

  • [Хопкрофт-Пол-Валиант]. Они доказывают, что D T I M E ( n ) D S P A C E ( n / log n ) (недиагонализирующая часть их доказательства), а затем используют тот факт, чтоCSLDTIME(n)DTIME(n)DSPACE(n/logn)CSL=NSPACE(n)в сочетании с пространственной иерархией. Их результат + пространственная иерархия также подразумевает .DSPACE(n)DTIME(n)
  • Пространственно-временные компромиссы для удовлетворения (см., Например, введение Бусс-Уильямса и ссылки в нем)
  • [Пол-Пиппингер-Семереди-Троттер]. Использует нетривиальное моделирование любой детерминированной машины суперлинейного времени на более быстрой машине с четырьмя чередованиями в сочетании с детерминированной иерархией времени.DTIME(n)NTIME(n)
  • Однородные нижние оценки перманента [ Аллендер , Аллендер-Гор , Койран-Перифель ]
  • [Уильямс] (хотя технически это неоднородная нижняя граница, она использует кучу умных идей в сочетании с недетерминированной иерархией времени)NEXPACC0
Джошуа Грохов
источник
4

Является ли разделение AC0TC0 по Смоленскому то , что вы искали?

Arne
источник
1
Спасибо, что это хороший результат, но я ищу для разделений классах, а не схемы классов. uniform
Андрас Фараго
2
@AndresFarago: униформа AC ^ 0 также правильно включена в униформу TC ^ 0.
Эмиль Йержабек поддерживает Монику
2
@ EmilJeřábek: Есть ли доказательство того, что равномерно правильно содержится в равномерном T C 0, что также еще не доказывает неравномерное утверждение? (Если нет, то, по-видимому, ваш пример подпадает под общий принцип, что неоднородные нижние границы сильнее, чем однородные нижние границы, и я думаю, что OQ пытался избежать таких ответов ...)AC0TC0
Джошуа Грохоу
2
Я думаю, что неоднородность в доказательствах является вторичной по отношению к тому факту, что это довольно маленькие классы, где у нас есть некоторое хорошее комбинаторное / алгебраическое понимание их. Т.е. мы понимаем их достаточно хорошо, чтобы непосредственно построить объект, которого нет в них. Для больших классов такого понимания нет, и поэтому единственный известный нам метод - это диагонализация всего класса для создания таких объектов.
Kaveh
2

Еще один нетривиальный пример связан со средним уровнем сложности. Райнер Шулер доказывает интересные свойства класса, который он называет , см. [1].PPcomp

- это класс языков, которые принимаются за полиномиальное время по µ- среднему значению длякаждоговычисляемого (P-вычислимого) распределениязаполиномиальное время µ . Естественно, что P P P - с о т р имеет место, так как существование алгоритма детерминированного полиномиальногоозначаетчто он остается эффективным в среднем, независимотогочто распределение входного сигнала. Однако условие работы в среднем полиномиальном времени длякаждогоPPcompμμPPPcomp P-вычисляемого входного распределения кажется достаточно сильным, чтобы заподозрить .PPcomp=P

Удивительно, но Шулер доказывает , что существует язык , который является Тьюринг-полным для Е , то есть Е Р Р Р - с о м рLPPcompE Это подразумевает безусловное разделение Р Р - с о м пP . В то время как последний также использует факт E

EPPPcomp()
PPcompP , который следует из теоремы иерархии времени, новая часть (*) основана на различных инструментах: помимо диагонализации, она использует ограниченную ресурсом меру и колмогоровскую сложность.EP

Ссылка:

[1] Р. Шулер, «Закрытие таблицы истинности и замыкание по Тьюрингу среднего полиномиального времени имеют разные показатели в EXP», CCC 1996, pdf

Андрас Фараго
источник