Algumas questões sobre computação paralela e a classe NC

14

Eu tenho várias perguntas relacionadas sobre esses dois tópicos.

Primeiro, a maioria dos textos de complexidade apenas encobre a classe . Existe um bom recurso que cubra a pesquisa com mais profundidade? Por exemplo, algo que discute todas as minhas perguntas abaixo. Além disso, estou assumindo que ainda vê uma boa quantidade de pesquisa devido ao seu vínculo com a paralelização, mas posso estar errado. A seção no zoológico de complexidade não ajuda muito.N CNCNC

Segundo, a computação em um semigrupo está em se assumirmos que a operação do semigrupo leva tempo constante. Mas e se a operação não levar tempo constante, como é o caso de números inteiros ilimitados? Existem problemas conhecidos com o ?N C iNC1NCEu

Terceiro, desde que , existe um algoritmo para converter qualquer algoritmo de espaço de log em uma versão paralela?euNC2

Quarto, parece que a maioria das pessoas assume que da mesma maneira que . Qual é a intuição por trás disso?PN PNCPPNP

Quinto, todo texto que li menciona a classe mas não fornece exemplos de problemas que ela contenha. Há alguns?RNC

Finalmente, esta resposta menciona problemas em com o tempo de execução paralela sublinear. Quais são alguns exemplos desses problemas? Existem outras classes de complexidade que contêm algoritmos paralelos desconhecidos em ?N CPNC

Mike Izbicki
fonte
1
Além disso, observe esta pergunta semelhante.
Nicholas Mancuso

Respostas:

9

Terceiro, desde , existe um algoritmo para converter qualquer algoritmo de espaço de log em uma versão paralela?LNC2

Pode ser mostrado (Arora e Barak livro) dada uma -tempo TM M , que uma alheio TM M ' (isto é, uma TM cujo movimento da cabeça é independente da sua entrada x ) pode-se construir um circuito de C n a calcular H ( x ) , onde | x | = n .t(n)MMxCnM(x)|x|=n

O esboço prova é ao longo das linhas de ter simular M e definindo "instantâneos" de seu estado (isto é, posições da cabeça, símbolos em cabeças) a cada passo de tempo t i (pensar de um log computacional). Cada passo t i pode ser calculado a partir de x e o estado t i - 1 . Porque cada instantâneo envolve apenas uma cadeia de tamanho constante-, e existe apenas uma quantidade constante de cordas de que o tamanho, o instantâneo no t i pode ser calculado por um circuito de tamanho constante,.MMtEutEuxtEu-1tEu

Se você compor os circuitos de tamanho constantes-para cada temos um circuito que calcula M ( x ) . Usando esse fato, juntamente com a restrição de que a linguagem de M está em L , vemos que nosso circuito C n é, por definição , uniforme de espaço de log , onde uniformidade significa apenas que nossos circuitos em nossa família de circuitos { C n } computam M ( x ) todos têm o mesmo algoritmo. Não é um algoritmo personalizado para cada circuito que opera no tamanho de entrada n .tEuM(x)MeuCn{Cn}M(x)n

Novamente, a partir da definição de uniformidade, vemos que os circuitos que decidem qualquer idioma em devem ter um tamanho de função ( n ) computável em O ( log n ) . A família de circuitos A C 1 tem no máximo profundidade O ( log n ) .euTamanho(n)O(registron).UMAC1O(registron)

Finalmente, pode-se demonstrar que fornece a relação em questão.UMAC1NC2

Em quarto lugar, parece que a maioria das pessoas assumem que da mesma forma que PN P . Qual é a intuição por trás disso?NCPPNP

Antes de prosseguirmos, vamos definir o que significa completude.P

Um idioma é P - completo se L P e todo idioma em P tiver espaço de log redutível a ele. Além disso, se L for P -complete, o seguinte é verdadeiroeuPeuPPeuP

  1. euNCP=NC

  2. eueuP=eu

Agora, consideramos a classe de linguagens decidida eficientemente por um computador paralelo (nosso circuito). Existem alguns problemas em P que parecem resistir a qualquer tentativa de paralelização (isto é, programação linear e problema de valor do circuito). Ou seja, certos problemas exigem que a computação seja feita passo a passo.NCP

Por exemplo, o problema do valor do circuito é definido como:

Dado um circuito , entrada x e uma porta g C , qual é a saída de g em C ( x ) ?CxgCgC(x)

Não sabemos como calcular isso melhor do que calcular todos os portões que vêm antes de g . Dado alguns deles podem ser computados em paralelo, por exemplo, se tudo ocorrer em algum instante temporal t i , mas não sei como calcular a saída de portões em timestep t i e timestep t i + 1 para a dificuldade óbvia que portões em t i + 1 exigem a saída de gates na t i !ggtEutEutEu+1tEu+1tEu

Esta é a intuição atrás .NCP


Limits to Parallel Computation é um livro sobre Completeness na mesma linha do livro N P- Completeness da Garey & Johnson .PNP

Nicholas Mancuso
fonte
Obrigado pelas 2 referências e pela resposta parcial. O livro Limites à computação paralela faz um trabalho melhor do que os outros livros que eu examinei, mas ainda é relativamente antigo e não é tão completo quanto eu gostaria.
Mike Izbicki
3

Quinto, todo texto que li menciona a classe RNC, mas não dá exemplos de problemas que ela contém. Há alguns?

O artigo "Combinar é tão fácil quanto a inversão de matrizes" de Mulmuley, Vazirani e Vazirani tem vários exemplos de problemas na classe . A principal delas é encontrar uma correspondência máxima, então eles reduzem outros problemas a essa.RNC2

Mike Izbicki
fonte