Обобщает ли теорема о пространственной иерархии неравномерное вычисление?

11

Общий вопрос

Обобщает ли теорема о пространственной иерархии неравномерное вычисление?

Вот несколько более конкретных вопросов:

  • Является ли ?L/polyPSPACE/poly

  • Для всех космических построимых функций , является D S Р С Е ( О ( е ( п ) ) ) / р о л у Д С Р С Е ( ф ( п ) ) / р ö л у ?f(n)DSPACE(o(f(n)))/polyDSPACE(f(n))/poly

  • Для каких функций известно, что: для всех конструктивных пространств f ( n ) , D S P A C E ( o ( f ( n ) ) ) / h ( n ) D S P A C E ( f ( n ) ) / h ( n ) ?h(n)f(n)DSPACE(o(f(n)))/h(n)DSPACE(f(n))/h(n)

Майкл Вехар
источник

Ответы:

7

Одна неоднородная «иерархия пространства», которую мы можем доказать, - это иерархия размеров для ветвящихся программ . Для булевой функции пусть B ( f ) обозначает наименьший размер разветвляющейся программы, вычисляющей f . Посредством аргумента, аналогичного этому аргументу иерархии для размера схемы , можно показать, что существуют константы ϵ , c, так что для каждого значения b ϵ 2 n / nе:{0,1}N{0,1}В(е)еε,сбε2N/N, существует функция такая, что b - c n B ( f ) b .е:{0,1}N{0,1}б-сNВ(е)б

Я думаю, что отделить от L / poly было бы сложно. Это эквивалентно доказательству того, что некоторый язык в P S P A C E имеет суперполиномиальную сложность программы ветвления. Простой аргумент показывает, что P S P A C E не имеет программ разветвления фиксированного полиномиального размера:пSпAСЕ/полиL/полипSпAСЕпSпAСЕ

Предложение. Для каждой постоянной , существует язык L P S P С Е так , что для всех достаточно больших п , B ( L п ) > п к . (Здесь L n - индикаторная функция для L { 0 , 1 } n .)КLпSпAСЕNВ(LN)>NКLNL{0,1}N

Доказательство. По доказанной нами иерархии существует ветвящаяся программа размера n k + 1, которая вычисляет функцию f с B ( f ) > n k . В полиномиальном пространстве, мы можем перебрать все ветвящиеся программы размера п к + 1 , всем ветвящимся программам размера п к и всем входам длины п найти такое разветвление программы P . Тогда мы можем смоделировать P для вычисления f .пNК+1еВ(е)>NКNК+1NКNппе

Уильям Хоза
источник