O teorema da hierarquia espacial generaliza para computação não uniforme?

11

Pergunta Geral

O teorema da hierarquia espacial generaliza para computação não uniforme?

Aqui estão algumas perguntas mais específicas:

  • L/polyPSPACE/poly

  • Para todas as funções construtivas de espaço , ?D S P A C E ( o ( f ( n ) ) ) / p o l y D S P A C E ( f ( n ) ) / p o l yf(n)DSPACE(o(f(n)))/polyDSPACE(f(n))/poly

  • Para que funções é sabido que: para todo o espaço construtível , ?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)

Michael Wehar
fonte

Respostas:

7

Uma "hierarquia espacial" não uniforme que podemos provar é uma hierarquia de tamanho para programas de ramificação . Para uma função booleana , deixe denotar o menor tamanho de um programa de ramificação computando . Por um argumento análogo a este argumento da hierarquia para o tamanho do circuito , pode-se mostrar que existem constantes ; para cada valor , existe uma função modo que .B ( f ) f ε , c b ε 2 n / n f : { 0 , 1 } n{ 0 , 1 } b - c n B ( f ) bf:{0,1}n{0,1}B(f)fϵ,cbϵ2n/nf:{0,1}n{0,1}bcnB(f)b

Eu acho que seria difícil separar de . É equivalente a provar que alguma linguagem em possui complexidade de programa de ramificação super polinomial. Um argumento simples mostra que não possui programas de ramificação de tamanho polinomial fixo :L / poli P S P A C E P S P A C EPSPACE/polyL/polyPSPACEPSPACE

Proposição. Para cada constante , existe uma linguagem modo que, para todos os suficientemente grandes , . (Aqui é a função indicadora de .)L P S P A C E n B ( L n ) > n k L n L { 0 , 1 } nkLPSPACEnB(Ln)>nkLnL{0,1}n

Prova. Pela hierarquia que provamos, existe um programa de ramificação de tamanho que calcula uma função com . No espaço polinomial, que pode interagir sobre todos os programas de ramificação de tamanho , todos os programas de ramificação de tamanho , e todas as entradas de comprimento de encontrar tais ramificação um programa . Então podemos simular para calcular .n k + 1 f B ( f ) > n k n k + 1 n k n P P f fPnk+1fB(f)>nknk+1nknPPf

William Hoza
fonte