NC (complexidade)

Na teoria da complexidade, a classe NC (para "Classe de Nick") é o conjunto de Problema de decisão decidíveis em tempo polilogarítmico em um computador paralelo com um número polinomial de processadores. Em outras palavras, um problema é no NC se existem constantes c e k tal que ele pode ser resolvido no tempo O(logc n) usando O(nk) processadores paralelos. Stephen Cook deu o nome de "classe de Nick", depois de Nick Pippenger, que tinha feito uma extensa pesquisa sobre circuitos com profundidade polilogaritmica e tamanho polinomial. Tal como a classe P pode ser pensado como os problemas tratáveis (tese de Cobham), de modo NC podem ser considerados como os problemas que podem ser eficazmente resolvidos num computador paralelo. NC é um subconjunto de P porque computações paralelas polilogaritmicas podem ser simuladas por seqüenciais de tempo polinomial. Desconhece-se se NC = P, mas a maioria dos pesquisadores suspeitam que isso é falso, o que significa que provavelmente existem alguns problemas tratáveis que são "inerentemente sequencial" e não pode ser significativamente acelerada usando paralelismo. Tal como a classe NP-Completo pode ser pensado como "provavelmente intratável", por isso a classe P-Completa, ao utilizar reduções NC, pode ser pensado como "provavelmente não paralelizável" ou "provavelmente inerentemente sequencial". O computador paralelo na definição pode ser considerado como uma máquina de acesso aleatório paralelo (PRAM). Isso é um computador paralelo com uma grupo central da memória, e qualquer processador pode acessar qualquer bit de memória em tempo constante. A definição de NC não é afetado pela escolha do modo como o PRAM manipula o acesso simultâneo a um único bit, por mais do que um processador. Pode ser CRCW, CREW, ou EREW. Veja PRAM para descrições desses modelos. Equivalentemente, NC podem ser definidos como aqueles problemas de decisão decidíveis por um circuito booleano uniforme (o...