Procurando um bom problema dentro do SC, mas não nos dois primeiros níveis

18

O zoológico de complexidade não tem muito a ver com o . Estou procurando um bom problema de que esteja nos níveis mais altos da hierarquia, isto é, um problema no mas não se sabe que está em .SCDTimeSpace(nO(1),lgO(1)n)DTimeSpace(nO(1),lg2n)

Como uma questão paralela, existe algum motivo conhecido para encontrar exemplos de bons problemas em níveis mais altos de hierarquias ( , , , , etc.) mais difícil do que os primeiros níveis?ACNCSCPH

embora agradável não seja um termo matemático, acho que compreendemos intuitivamente o que significa, por exemplo, aceitar problema para MNTs é um problema artificial que as pessoas não estão interessadas nele, além de estarem completas para , enquanto o gráfico está colorindo O problema era interessante antes de ser conhecido por estar em / completo para e ainda é interessante além da classe de complexidade à qual pertence.NPNP

Kaveh
fonte
(1) “aceitar um problema para os MNTs não é um problema artificial que as pessoas não estejam interessadas nele, além de estar completo para o PN”: parece que você tem um “não” excessivo aqui.
Tsuyoshi Ito
(2) “Como uma pergunta paralela, existe alguma razão conhecida para encontrar exemplos de bons problemas em níveis mais altos de hierarquias (CA, NC, SC, PH, etc.) ser mais difícil do que os primeiros níveis?” razão mais profunda do que "Níveis mais baixos são mais simples e, portanto, existem muitos bons exemplos neles"?
Tsuyoshi Ito
@ Tsuyoshi, obrigado, eu removi o extra não. Cerca de 2, sim, preciso de uma razão mais profunda para bons problemas que caem nos baixos níveis de hierarquias. Não vejo uma grande diferença de definição entre e digo . D T i m e S p a c e ( n O ( 1 ) , lg 4 n )DTEumeSpumace(nO(1),lg2n)DTEumeSpumace(nO(1),lg4n)
Kaveh
1
Claro que a definição é a mesma. A diferença é que log ^ 2 é mais simples que log ^ 4. O mesmo argumento se aplica ao perguntar por que existem muito mais algoritmos que são executados no tempo O (n ^ 2) do que aqueles que são executados no tempo O (n ^ 4).
Tsuyoshi Ito
@ Tsuyoshi, não sei o que você quer dizer com sendo mais simples que lg 2 . A questão também se aplica a P . lg4lg2P
Kaveh

Respostas:

12

Eu não tenho uma sugestão para um problema natural em , mas eu tenho uma sugestão para sua pergunta paralela, de por que encontrar tal problema parece difícil. Eu acho que isso tem algo a ver com a ideia popular de que as pessoas só podem realmente compreender (ou talvez só estejam interessadas em? Ou em ambas?) Matemática com algumas alternâncias quantificadoras profundas. Por exemplo, a definição de limite é de dois quantificadores de profundidade (para todo epsilon existe um delta ...); a definição de " L N PDTEumeSpumace(nO(1),registro4n)euNP"é dois quantificadores (existe uma máquina tal que para todas as entradas ...), e a instrução" "tem três quantificadores de profundidade.PNP

Com relação a , este é um pouco corroborada pelo facto de que existem muitos problemas naturais que são N P -completo, muitos problemas que são naturais Σ 2 P -completo, e apenas alguns problemas naturais conhecidos, que são Σ 3 P -complete (veja o compêndio de Schaefer e Umans ). A maioria dos problemas naturais conhecidos para ser completa para níveis mais elevados de P H vir da própria lógica, que é menos surpreendente, uma vez dentro de um dado uma lógica muitas vezes tem a noção de " kPHNPΣ2PΣ3PPHk- muitas alternativas de quantificador ", ou pelo menos uma maneira natural de simulá-lo. Elas talvez se enquadram na mesma categoria de" aceitação de problemas para NTMs ", que você declarou" não é agradável o suficiente "para esta pergunta.

Também vale a pena mencionar que o mesmo acontece no mundo da computabilidade, o que talvez sugere que isso tenha mais a ver com o entendimento de quantificadores alternados e menos com a complexidade em si. Sabe-se que muitos problemas naturais são completos ou (equivalentes ao problema de parada) e muitos problemas naturais são completos para o segundo e o terceiro níveis da hierarquia aritmética. Mas à medida que você avança para níveis mais altos da hierarquia aritmética, sabe-se que cada vez menos problemas naturais estão completos para esses níveis. Não tenho certeza se conheço um problema natural completo para Σ 0 4 e nunca ouvi falar de um problema natural completo para Σ 0 5Σ10 0Σ40 0Σ50 0 (embora talvez exista).

Com relação aos limites do espaço polilogarítmico, acho que um raciocínio semelhante se aplica, mas ainda mais. Como , mesmo problemas que estão nos "primeiros poucos" níveis da " hierarquia N L " são todos de fato em N L (a hierarquia entra em colapso ), que está contido no espaço do log-quadrado.Neu=coNeuDSPUMACE(registro2n)NeuNeu

Joshua Grochow
fonte
2
Esta é uma resposta muito interessante.
Suresh Venkat
1
Obrigado Joshua, esta é realmente uma boa observação. Isso meio que sugere uma perspectiva epistemológica: o que parece natural para os seres humanos é de complexidade quantificadora limitada.
Kaveh