Separação de classes com diferentes quantidades de conselhos?

O teorema da hierarquia de tempo permite mostrar que, por exemplo, existem problemas em P que não podem ser resolvidos no tempo menos que const * n ^ 2 por uma máquina de Turing. Mas dê alguns conselhos à máquina de Turing e todas as apostas estão fora. Ainda não se pode mostrar que mesmo um circuito de tamanho linear não pode resolver todo o PSPACE. Então, e se tentarmos comparar duas classes diferentes nas quais ambas têm conselhos? Por exemplo, pode-se separar o espaço polinomial com orientação logarítmica do tempo linear com orientação linear? Essa é apenas uma pergunta de exemplo inventada, estou me perguntando que resultados gerais existem nesse sentido.

Seja alguma função. Pode-se provar que:$s(n) \ge n$

$\mathbf{DSIZE}(s) \subseteq \mathbf{DTIME}(s^2) / F(O(s\log s))$

$\mathbf{DSIZE}(s)$$s$$\mathbf{K/F}$$\mathbf{K}$$\mathbf{F}$

$F(f) = \left\{h \colon \{0,1\}^* \to \{0,1\}^* \mid |h(x)| \le f(|x|) \text{ for all } x\right\}$

$d(n) \ge \log n$

$\mathbf{DDEPTH}(d) \subseteq \mathbf{DSPACE}(d) / F(2^{O(d)})$

$\mathbf{DDEPTH}(d)$$d$

Editar: mais duas inclusões:

Para , temos$t(n) \ge n$$\mathbf{DTIME}(t) \subseteq \mathbf{DSIZE}(t \log t)$$l(n) \ge \log n$$\mathbf{NSPACE}(l) \subseteq \mathbf{DDEPTH}(l^2)$

Para provas, consulte a seção 2-3 do livro de Heribert Vollmer .

Usando essas inclusões e hierarquias de tempo / espaço, é possível construir hierarquias para classes de complexidade não uniformes.

Edição 2:

Você pode combinar os resultados acima com os seguintes resultados em hierarquias para classes com conselhos:

1. Hierarquias temporais para cálculos com alguns conselhos .
2. Limites Incondicionais Incondicionais Contra Conselhos .