Quais hierarquias e / ou teoremas de hierarquia você conhece?

Atualmente, estou escrevendo uma pesquisa sobre teoremas de hierarquia no TCS. Pesquisando artigos relacionados, notei que a hierarquia é um conceito fundamental não apenas no TCS e na matemática, mas em várias ciências, da teologia e sociologia à biologia e química. Visto que a quantidade de informações é vasta, espero poder pedir alguma ajuda por esta comunidade. Obviamente, não quero que você faça uma pesquisa bibliográfica para mim, mas estou pedindo dois tipos de informações:

1. Hierarquias e teoremas de hierarquia que são o resultado do seu trabalho ou do trabalho de seus colegas ou de outras pessoas com as quais você está familiarizado e acha que isso não é tão conhecido. Pode ser, por exemplo, um teorema da hierarquia para um modelo de computação obscuro no qual você esteja interessado ou uma hierarquia de classes específicas, por exemplo, relacionadas à teoria dos jogos.

2. Hierarquias e teoremas de hierarquia que você considera absolutamente necessários para serem incluídos em uma pesquisa desse tipo. Isso provavelmente já me seria conhecido, mas seria útil ver quais hierarquias você considera mais importantes e por quê. Pode ser do tipo "considero $PH$ muito importante porque, sem ela, não poderíamos fazer esse tipo de pesquisa" ou "Embora não seja tão conhecido, no TCS baseado em lógica, usamos constantemente essa hierarquia e eu" considerá-lo uma ferramenta importante ". . E sim, acredito que as pessoas da lógica têm muitas hierarquias para mencionar, mas lembre-se de que estamos falando de hierarquias de problemas.

Vou manter uma lista atualizada aqui:

• $DTIME$ Hierarquia
• $NTIME$ Hierarquia
• $SPACE$Hierarquia S P A C E
• Hierarquia aritmética (também conhecida como Kleene)
• Hierarquia Hiperaritmética
• Hierarquia Analítica
• Hierarquia de Chomsky
• Hierarquia de Grzegorczyk e afins: hierarquia de Wainer (crescimento rápido), hierarquia de Hardy
  (crescimento lento) e hierarquia de Veblen
• Hierarquia de Ritchie
• Hierarquia do Axt (conforme definido no Axt63 )

• A hierarquia de loop (definida em MR67 )

• Hierarquia N $NC$ ($AC$ ,$ACC$ )

• A hierarquia de profundidade, conforme definida em Sipser83
• Hierarquia polinomial ( ) e a hierarquia Meyer-Stockmeyer menos refinado (sem dinstinction entre quantificadores)$PH$
• Hierarquia exponencial ( )$ELEMENTARY$

• - Hierarquia intermediária (teorema de Ladner) $NP$

• A não tão resistente (Arthur-Merlin)$AM$

• A (Fixed-Parâmetro não-determinístico) hierarquia e a hierarquia alternada W (relacionada Um W -hierarchy) e W * -hierarchy (W com Parâmetro-Dependente Profundidade)$W$$AW$$W^{*}$
• Hierarquia de contagem
• Hierarquia de Fourier
• Hierarquia Booleana (acima de ), também igual à Hierarquia de Consulta (acima de N P )$NP$$NP$
• Hierarquias para teste de propriedade, como visto em GoldreichKNR09
• A hierarquia de profundidade de pontos dos idiomas regulares sem estrelas
• : As classes solucionáveis ​​por programas de ramificação de tamanho polinomial, com a condição adicional de que cada bit da entrada é testado na maioria dos d vezes, formam uma hierarquia para diferentes valores de$BP_{d}(P)$$d$
• A hierarquia de tempo para a complexidade do circuito
• A hierarquia polinomial na complexidade da comunicação

Nota: Se você não quiser ser mencionado exclusivamente, diga-o. Como regra geral, mencionarei a comunidade e também a pessoa específica que traz novas informações à tona.

A Hierarquia de Fourier, conforme definido em " Yaoyun Shi, Quantum e trocas clássicas ".

Do zoológico de complexidade :

$\mathsf{FH}_k$ é a classe de problemas que podem ser resolvidos por uma família uniforme de circuitos quânticos de tamanho polinomial, com$k$níveis de portões de Hadamard e todas as outras portas de preservação a base computacional.

• $\mathsf{FH}_0 = \mathsf{P}$
• $\mathsf{FH}_1 = \mathsf{BPP}$
• $\mathsf{FH}_2$ contém factoring porque dealgoritmo de estimativa de fase do Kitaev.

É um problema em aberto mostrar que a hierarquia de Fourier é infinita em relação a um oráculo (ou seja, $\mathsf{FH}_k$ está estritamente contido em $\mathsf{FH}_{k+1}$ ).

- Na linha das "anti-hierarquias", vale a pena mencionar o teorema da diferença de Borodin .

Teorema. Para cada função computável total tal que f ( n ) = Ω ( n ) , existe um total computável g : N → N tal que T I M E [ g ( n ) ] = T I M E [ f ( g ( n ) ) ] .$f : {\mathbb N} \rightarrow {\mathbb N}$$f(n) = \Omega(n)$$g : {\mathbb N} \rightarrow {\mathbb N}$${\sf TIME}[g(n)] = {\sf TIME}[f(g(n))]$

Isso contradiz o teorema da hierarquia de tempo, exceto que não é construtível no tempo (de fato, é por isso que devemos ter suposições de construtibilidade nas declarações da maioria das hierarquias de complexidade).$g$

- Há também reforços interessantes das hierarquias de tempo usuais, como:

(existem problemas no tempo não podem ser resolvidos com sucesso a qualquer momento máquina do tempo usando bits de conselhos, mesmo em comprimentos de entrada infinitos). A prova é fácil: vamos listar as máquinas do tempo que recebem bits de conselhos como segunda entrada. Defina que divide em onde, executa e gera a resposta oposta. Então .n k - 1 n - log n { M i } n k - 1 n - log n M ′ ( x ) x x = y z | z | = log | x | M z ( x , y ) L ( M ′ ) ∉ i . o . - T I $n^k$$n^{k-1}$$n-\log n$$\{M_i\}$$n^{k-1}$$n-\log n$$M'(x)$$x$$x=yz$$|z|=\log |x|$$M_z(x,y)$$L(M') \notin i.o.{\sf -TIME}[n^{k-1}]/(n-\log n)$

- A falta de hierarquias de tempo conhecidas em determinadas situações deve ser considerada (como problemas em aberto). Por exemplo, ?${\sf BPTIME}[n] = {\sf BPP}$

O Zoológico de Complexidade fornece algumas hierarquias . Entre eles, a Hierarquia de Contagem e a Hierarquia Booleana já não foram citadas.

[EDIT] Para tornar minha resposta mais informativa, uma rápida definição da Hierarquia de Contagem.

• ${\sf C_0P} = {\sf P}$
• ${\sf C_1P} = {\sf PP}$
• ${\sf C_{k+1}P} = {\sf PP^{C_kP}}$

Então, quanto à hierarquia polinomial, é definido como .$\sf CH$$\bigcup_k {\sf C_kP}$

A hierarquia de contagem foi definida por Wagner [Wag86]. Links para a teoria dos circuitos limiares foram descobertos por Allender & Wagner [AW93]. Muito mais recentemente, Bürgisser [Bür09] também usou a hierarquia de contagem para relacionar o modelo de Valiant à conjectura de Shub e Smale. Em particular, ele provou que a conjectura implica um limite inferior superpolinomial para a permanente.$\tau$$\tau$

[Wag86] KW Wagner. A complexidade de problemas combinatórios com representação sucinta de entradas . Acta Mathematica 23 (3), 325-356, 1986.
[AW93] E. Allender & KW Wagner. Hierarquias de contagem: tempo polinomial e circuitos de profundidade constante . Current Trends in Computer Science , 469-483, 1993.
[Bür09] P. Bürgisser. Na definição de números inteiros e na prova do circuito aritmético, limite inferior . Computacional Complexidade 18 (1), 81-103, 2009.

Goldreich et. al. ter teoremas de hierarquia para teste de propriedade:

• Oded Goldreich, Michael Krivelevich, Ilan Newman, Eyal Rozenberg: Teoremas da Hierarquia para Teste de Propriedade. Teste de propriedade , notas de aula em ciência da computação, vol. 6390, pp. 289-294, Springer, 2010.

Também no ECCC .

Sipser mostrou uma hierarquia de profundidade dentro de , ou seja, que os circuitos de profundidade de tamanho poli são mais poderosos do que os circuitos de profundidade de tamanho poli: d + 1 $AC^0$$d+1$$d$

Sipser, M. Borel define e complexidade do circuito . STOC 1983.

Dieter van Melkebeek e co-autores têm hierarquias de tempo e espaço para modelos semânticos com conselhos, incluindo randomização.

• Dieter van Melkebeek, Konstantin Pervyshev: uma hierarquia de tempo genérica com um pouco de conselho . Complexidade Computacional 16 (2): 139-179 (2007)
• Jeff Kinne, Dieter van Melkebeek: resultados da hierarquia espacial para modelos aleatórios e outros modelos semânticos . Computational Complexity 19 (3): 423-475 (2010)

Aqui estão mais hierarquias para classes semânticas com conselhos. Especificamente, para ZPTIME e RTIME.

Lance Fortnow, Rahul Santhanam, Luca Trevisan. Hierarquias para classes semânticas . Em STOC'05.

Existe a hierarquia de Zheng-Weihrauch para números reais

X. Zheng e K. Weihrauch. A hierarquia aritmética dos números reais . Lógica Matemática Trimestral.Vol. 47 (2001), nº 1 51 - 65.

Existe uma classe , definida em um artigo de 1975 por L. Adelman e K. Manders, que é um análogo diofantino da classe . Um idioma está contido em se houver um polinômio tal que Se é igual a é um problema em aberto. Essa igualdade mostraria conexões entre teoria dos números e ciência da computação.$\mathsf{D}$$\mathsf{NP}$$L$$\mathsf{D}$$P$

Existe um análogo diofantino da hierarquia polinomial, chamado "hierarquia diofantina". As hierarquias polinomial e diofantina estão entrelaçadas:

Outra hierarquia estrita: programas de ramificação que testam cada bit apenas um número limitado de vezes. Quanto mais testes forem permitidos, maior a classe de programas de ramificação. Geralmente, os programas de ramificação também são restritos ao tamanho polinomial. BP _d (P) é a classe de programas de ramificação de tamanho polinomial que podem testar cada bit até vezes.$d$

L / poli é a união da BP _d (P) sobre todos os d , enquanto a BP _d-1 (P) BP _d (P) para cada d .$\subsetneq$

Na teoria da complexidade parametrizada , existem várias hierarquias, embora apenas a hierarquia já mencionada apareça frequentemente nas publicações. Outros são:$\mathsf{W}$

• $\mathsf{A}$ mathsf
• $\mathsf{AW}$ mathsf
• $\mathsf{EW}$ -hierarchy
• $\mathsf{LOG}$ mathsf
• $\mathsf{M}$ -hierarchy
• $\mathsf{S}$ math s
• $\mathsf{W^∗}$ -hierarchy
• $\mathsf{W^{func}}$ -hierarchy

Eles são todos descritos na teoria da complexidade parametrizada, Flum e Grohe, Birkhäuser, 2006 .

Não tenho certeza se isso se encaixa nos seus critérios, mas existe a hierarquia de profundidade de pontos dos idiomas regulares sem estrelas.

A hierarquia para o tamanho do circuito, veja a pergunta anterior .

A teoria das linguagens regulares das árvores infinitas deu origem a várias hierarquias, atualmente estudadas, com muitas questões ainda em aberto.

Ao usar autômatos em árvores infinitas, a condição de paridade (ou condição Mostowski) é de especial interesse, porque os autômatos de paridade não determinísticos podem expressar todos os idiomas regulares das árvores ininitas, e a estrutura da condição de aceitação é mais simples do que outras como Rabin ou Müller. .

$[i,j]$$i\in\{0,1\}$$i\leq j$$L$$[i,j]$$L$$[i,j]$

• hierarquia determinista de Mostowski (nem todas as línguas regulares)
• hierarquia Mostowski não determinística
• hierarquia Mostowski alternada

$\Sigma_2\cap \Pi_2$$L$

• hierarquia de índice fraca (nem todos os idiomas regulares)

$L$

$G_i$$\mathsf{PH}$$C \subset \mathsf{P}$$C$

$\mathsf{S^i_j}$

Aqui está uma nova hierarquia para idiomas sem contexto por Tomoyuki Yamakami.

$CFL$$CFL^{CFL}$

Elaborando um dos pontos de referência mencionados pelo OP (GoldreichKNR09): existem vários teoremas de hierarquia nos testes de propriedades e provas de proximidade, relacionados à complexidade da consulta, à adaptabilidade ou à testabilidade em relação ao número de rodadas (para provas de proximidade). Veja, por exemplo,

• Teoremas de hierarquia para testes de propriedades , Oded Goldreich, Michael KrivelevichIlan Newman e Eyal Rozenberg, 2012. https://link.springer.com/article/10.1007/s00037-011-0022-4 [mencionado pelo OP]
• Um teorema da hierarquia para provas interativas de proximidade , Tom Gur e Ron Rothblum, 2017. http://drops.dagstuhl.de/opus/volltexte/2017/8153/
• Teoremas de Hierarquia para Teste de Propriedades na Complexidade de Consultas sem Tamanho , Oded Goldreich, 2018. https://eccc.weizmann.ac.il/report/2018/098/
• Um teorema da hierarquia de adaptabilidade para testes de propriedades , Clément Canonne e Tom Gur, 2018. https://link.springer.com/article/10.1007%2Fs00037-018-0168-4

A partir dessa pergunta no cs.stackexchange , tomei conhecimento da hierarquia de gênero das linguagens regulares . Essencialmente, você pode caracterizar idiomas regulares com base na superfície mínima do gênero na qual o gráfico do DFA pode ser incorporado. É mostrado em [1] que existem idiomas de gênero arbitrariamente grande e que essa hierarquia é adequada.

1. Bonfante, Guillaume e Florian Deloup. " O gênero das linguagens regulares. " Estruturas Matemáticas em Ciência da Computação 28.1 (2018): 14-44.

Contando Hierarquia Polinomial, #PH, para abreviar. O primeiro nível é #P, depois #NP ... etc.

$^{cc}$

$D_{p}$

$NC^{k}$$AC^{k}$$P$$PSPACE$$P$$UP$

Relacionadas para um estudo mais aprofundado de conectivos booleanos, e o isomorfismo de grafos são as hierarquias baixa e alta , também referência da Wikipedia .

Mais sobre o lado obscuro: meu teorema da hierarquia de segunda ordem para lógicas de ponto fixo na teoria de modelos finitos. Veja ainda outro teorema da hierarquia .