Por que consideramos o espaço de log como um modelo de computação eficiente (em vez do espaço de polilog)?

49

Essa pode ser uma pergunta subjetiva, e não uma resposta concreta, mas de qualquer maneira.

Na teoria da complexidade estudamos a noção de cálculos eficientes. Existem classes como significa tempo polinomial e significa espaço no log . Ambos são considerados representados como uma espécie de "eficiência" e capturam muito bem as dificuldades de alguns problemas.LPL

Mas há uma diferença entre e : enquanto o tempo polinomial, , é definido como a união de problemas que são executados no tempo para qualquer constante , isso é,L P O ( n k ) kPLPO(nk)k

P=k0TIME[nk] ,

o espaço do log, , é definido como . Se imitarmos a definição de , torna-seS P A C E [ log n ] PLSPACE[logn]P

PolyL=k0SPACE[logkn] ,

onde é chamado de classe de espaço polylog . Minha pergunta é:PolyL

Por que usamos o espaço de log como a noção de computação eficiente, em vez do espaço polylog?

Uma questão principal pode ser sobre os conjuntos completos de problemas. No espaço de registro, muitas reduções de uma, e têm problemas completos. Por outro lado, se tiver problemas completos com essas reduções, teríamos contraditado o teorema da hierarquia espacial. Mas e se mudarmos para as reduções do polilog? Podemos evitar esses problemas? Em geral, se tentarmos encaixar na noção de eficiência e (se necessário) modificar algumas das definições para obter todas as boas propriedades que uma classe "boa" deve ter, até onde podemos ir?L P o l y L P o l y LPLPolyLPolyL

Existe alguma razão teórica e / ou prática para usar o espaço do log em vez do espaço polylog?

Hsien-Chih Chang 張顯 之
fonte
Hsien-Chih, boa pergunta.
Mohammad Al-Turkistany
9
É sabido que . Até onde eu sei, a relação exata entre e não é clara. Por exemplo, é possível que alguns problemas sejam solucionáveis ​​em e não solucionáveis ​​em E vice-versa. (Na verdade, isso parcialmente sua pergunta sobre por que o é um candidato estranho a uma noção de computação eficiente.) Para um pouco mais sobre o , você pode conferir o livro de complexidade de Papadimitriou , especificamente os exercícios e discussões no final do Capítulo 16.P p o l Y L P S L Y L P p o l Y L P S L Y LpolyLPPpolyLpolyLP polyLpolyL
Daniel Apon
Na verdade, um outro comentário rápido sobre um pedaço menor da sua pergunta geral: reduções espaço polylog não vai dizer muito sobre , pelas mesmas razões redução em tempo polinomial não dizer muito sobre . PpolyLP
Daniel Apon
@ Daniel Apon: Obrigado por mencionar o livro, e isso é bom :) Para o segundo comentário, pelo mesmo argumento, podemos usar reduções lineares em vez de polinomiais para obter mais informações sobre , certo? P
Hsien-Chih Chang,
Chih Chang: Bem, eu não sei sobre reduções em tempo linear por exemplo, mas não são outros, noções interessantes de reduções que dão informações sobre a complexidade dentro . P
Daniel Apon

Respostas:

51

A menor classe que contém tempo linear e fechada em sub-rotinas é P. A menor classe que contém espaço em log e fechada em sub-rotinas ainda é espaço em log. Portanto, P e L são as menores classes robustas de tempo e espaço, respectivamente, e é por isso que elas se sentem bem ao modelar computação eficiente.

Lance Fortnow
fonte
4
Parece a melhor resposta para a pergunta real.
Derrick Stolee
11
Entre todas essas boas respostas, acho que a resposta de Lance é a mais precisa, e aceito. Mas ainda muito obrigado a todas as respostas atenciosas!
Hsien-Chih Chang,
11
Além disso, é um problema em aberto se P = L.
Diego de Estrada
25

Um problema é que não se sabe se . Isso praticamente mata a noção de eficiência. Em outra nota, determinar se a interseção dos idiomas reconhecidos pelos autômatos não está vazia é sob reduções do espaço de log [Lange-Rossmanith] . Talvez haja alguns problemas semelhantes para o espaço polilogístico determinístico.SPACE[log2n]Plogk1(n)NSPACE[logkn]-complete

A classe foi estudada no passado. [Cook] provou isso . Conforme observado por Derrick Stolee, essa classe agora é conhecida como e foi generalizada para . Mais informações aqui .PLOSS=kTISP[nk,klog2n]DCFLPLOSSSC2SCk

Michael Blondin
fonte
2
Podemos usar vez de ? QuasiP=k0TIME[2logkn]P
Hsien-Chih Chang #
Esse é um problema em aberto conhecido? Você poderia fornecer uma referência?
Mohammad Al-Turkistany
Sua classe PLOSS é a mesma que em termos modernos. SC significa "Steve's Class", provavelmente o resultado de Cook que você cita. SC2
Derrick Stolee
5
Note-se que SC foi nomeado por Nick Pippenger, em um arranjo supostamente recíproco com Steve Cook para citar NC depois dele :)
Suresh Venkat
isso está correto: como é uma classe MUITO importante que representa eficiência, em vez de mudar de para para ajustar , usamos para ajustar ? Então, se em algum momento a relação for comprovada para algum , a classe se tornará mais importante? PPQuasiPpolyLLPSPACE[logkn]PkLk
Hsien-Chih Chang,
20

O espaço de log garante tempo polinomial, uma vez que existem no máximo de uma determinada máquina de Turing para espaço de log. Os problemas completos de Alcance Indireto e Alcance Direcionado (para L e NL, respectivamente) são muito "legais" de se pensar.2O(logn)=poly(n)

Observe que sua definição de PolyL também fornece PolyL = NPolyL, pelo teorema de Savitch, uma vez que .NSPACE[logkn]SPACE[log2kn]

Quando o espaço polilog é considerado, o trabalho foi feito para considerar o espaço polilogial com tempo polinomial simultâneo, fornecendo à hierarquia SC: . SCk=TISP[poly(n),logkn]

Derrick Stolee
fonte
Se usarmos reduções de polilog, a acessibilidade se tornará um problema completo para ? (Acho que sim, pelo mesmo método de alcançabilidade que prova a alcançabilidade e um problema ) . N G P S L Y LpolyLNLpolyL
Hsien-Chih Chang,
Se você usar reduções de polilog para problemas com PolyL, o idioma estará completo com PolyL. {1}
Derrick Stolee
Você está certo, desculpe-me pela pergunta estúpida :(
Hsien-Chih Chang
13

Eu acho que todas as outras respostas são muito boas; Vou tentar dar uma perspectiva diferente sobre o assunto.

Não sei até que ponto P modela a computação "eficiente" no mundo real, mas gostamos da classe por causa de suas boas propriedades de fechamento e outras razões matemáticas. Da mesma forma, L também é uma boa aula devido a algumas das razões mencionadas acima.

No entanto, como você comentou, se relaxarmos nossa definição de "eficiente" para um tempo quase polinomial, então o PolyL também será eficiente. Poderíamos discutir a teoria da complexidade em que permitimos que as classes definidas com um limite logarítmico em algum recurso usem recursos de polilog. Da mesma forma, também relaxaríamos nossas definições de NC, NL etc. para permitir circuitos de tamanho quase polinomial. Se fizermos isso, NC 1 , L, NL e NC todos coincidem com a classe PolyL. Nesse sentido, PolyL é uma classe robusta, pois muitas classes naturais coincidem com ela. Para obter mais informações sobre a teoria da complexidade com log -> polylog e polynomial -> quase-polinomial, consulte Classes de circuitos de tamanho quasipolinomial de Barrington.

Outro motivo para estudar classes poliL ou similares como quase-AC 0 é que, embora uma separação oráculo entre (digamos) ParityP e PH implique que PARITY não esteja contida em AC 0 , a implicação inversa não é conhecida como verdadeira. Por outro lado, PARITY não está contido em quase-AC 0 se e somente se houver uma separação do oráculo entre ParityP e PH. Da mesma forma, as classes quase-TC 0 e quase-AC 0 são diferentes se e somente se houver uma separação oráculo entre CH e PH. Portanto, as classes de complexidade usuais, como PH, ModPH, CH etc., quando reduzidas por um exponencial para provar os resultados do oráculo, se transformam em versões quase polinomiais das classes usuais AC 0 , ACC 0 e TC0 respectivamente. Da mesma forma, o argumento usado no teorema de Toda (PH está contido em P PP ) pode ser usado para mostrar que quase-AC 0 está contido na profundidade 3 quase-TC 0 . (Não sei se a mesma conclusão é conhecida para as versões usuais dessas classes. Vi isso listado como um problema em aberto em alguns artigos.)

Robin Kothari
fonte
11
Sua resposta realmente ajuda, obrigado por compartilhar sua opinião. Estou impressionado que quase algo tenha sido estudado MUITO !!
Hsien-Chih Chang # 2/10