NC (complexidade)

Problema de Ciência da computação em aberto:

NC = P ?

(mais problemas em aberto da Ciência da computação)

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(log^c n) usando O(n^k) 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 que pode ser calculado a partir do comprimento da entrada) com profundidade polilogaritmicas e um número polinomial de portas.

RNC é um NC estendendo classe com acesso a aleatoriedade.

Problemas em NC

Tal como acontece com P, por um ligeiro abuso de linguagem, pode-se classificar os problemas de função e problemas da pesquisa como sendo em NC. NC é conhecido por incluir muitos problemas, incluindo

• Adição de inteiro, multiplicação e divisão;
• Multiplicação de matrizes, determinantes, inversa, rank;
• Polinomial GCD, por uma redução de álgebra linear usando matriz Sylvester (é aberto se inteiro GCD está em NC);
• Encontrar uma correspondência máxima.

Muitas vezes, os algoritmos para esses problemas tiveram de ser inventados separadamente e não podiam ser adaptado a partir de algoritmos bem conhecidos - eliminação de Gauss e algoritmo de Euclides conta com as operações realizadas sequencialmente. Pode-se contrastar ripple carry adder com um somador carry-lookahead.

A hierarquia NC

NCⁱ é a classe de problemas de decisão decidíveis por circuitos booleanos uniformes com um número polinomial de portões de , no máximo, duas entradas e profundidade O(logⁱ n), ou da classe dos problemas de decisão solúveis em tempo O(logⁱ n) com um computador em paralelo com um certo número de processadores polinomial . Claramente, temos

$\mathbf {NC} ^{1}\subseteq \mathbf {NC} ^{2}\subseteq \cdots \subseteq \mathbf {NC} ^{i}\subseteq \cdots \mathbf {NC}$

que constitui o NC- hierarquia.

Podemos referir as classes NC ao espaço classes de L e NL e AC.

$\mathbf {NC} ^{1}\subseteq \mathbf {L} \subseteq \mathbf {NL} \subseteq \mathbf {AC} ^{1}\subseteq \mathbf {NC} ^{2}\subseteq \mathbf {P} .$

As classes de NC são relacionadas com as classes de AC , que são definidos de forma semelhante , mas com portas com Fanin ilimitada . Para cada i , temos

$\mathbf {NC} ^{i}\subseteq \mathbf {AC} ^{i}\subseteq \mathbf {NC} ^{i+1}.$

Como conseqüência imediata desta , temos que NC = AC. Sabe-se que ambas as inclusões são rigorosas para i = 0 .

Da mesma forma, tem-se que NC é equivalente para os problemas que podem ser resolvidos numa máquina alternante de Turing restringidas a , no máximo, duas opções em cada passo com espaço O(log n ) e $(\log n)^{O(1)}$ alternâncias.

Examinando o problema : NC é adequada?

Uma grande questão em aberto na teoria da complexidade é ou não cada contenção na hierarquia NC é apropriada. Foi observado por Papadimitriou que , se NCⁱ = NCⁱ⁺¹ para algum i , em seguida, NCⁱ = NC^j para todos os j ≥ i, e , como resultado , o NCⁱ = NC. Esta observação é conhecido como colapso NC- hierarquia , porque até mesmo uma única igualdade na cadeia de contenções

${\textbf {NC}}^{1}\subseteq {\textbf {NC}}^{2}\subseteq \cdots$

implica que toda a hierarquia NC " cai " para baixo a algum nível i. Assim, há duas possibilidades:

1. ${\textbf {NC}}^{1}\subset \cdots \subset {\textbf {NC}}^{i}\subset ...\subset {\textbf {NC}}^{i+j}\subset \cdots {\textbf {NC}}$
2. ${\textbf {NC}}^{1}\subset \cdots \subset {\textbf {NC}}^{i}=...={\textbf {NC}}^{i+j}=\cdots {\textbf {NC}}$

Acredita-se que (1) é o caso , embora não haja prova da verdade de qualquer declaração ainda não foi descoberto.

Teorema de Barrington

Um programa de ramificação com n variáveis de largura k e comprimento m consiste de uma seqüência de m instruções. Cada uma das instruções é uma tupla (i, p, q), onde i é o índice da variável a ser verificada (1 ≤ i ≤ n), e p e q são funções de {1, 2, ..., k} para {1, 2, ..., k}. Os números 1, 2, ..., k são chamados estados do programa de ramificação. O programa inicia no estado 1, e cada instrução (i, p, q) muda o estado de x para p (x) ou q (x), dependendo se a iésima variável ou é 0 ou 1.

A família de ramificação de programas consiste em um programa de ramificação com n variáveis para cada n.

É fácil de mostrar que cada linguagem L em {0,1} podem ser reconhecidos por uma família de programas de ramificação de largura e comprimento de 4 exponencial, ou por uma família exponencial de largura e comprimento linear.

Cada linguagem regular em {0,1} podem ser reconhecidos por uma família de programas de ramificação de largura constante e linear do número de instruções (uma vez que o DFA pode ser convertido para um programa de ramificação). BWBP indica a classe de linguagens reconhecíveis por uma família de programas de ramificação limitada largura e comprimento polinomial.

Teorema de Barrington diz que é exatamente nonuniform NC¹. A prova utiliza o nonsolvability do grupo simétrico S₅.

O teorema é bastante surpreendente. Isto implica que a maioria função pode ser calculada por uma família de programas de ramificação de largura constante e tamanho polinomial, enquanto intuição pode sugerir que, para alcançar o tamanho polinomial, é necessário uma série linear de estados.

A prova do teorema de Barrington

Um programa de ramificação de largura constante e tamanho polinomial pode ser facilmente convertido (via de divisão e conquista ) a um circuito de NC¹ .

Por outro lado , suponha que um circuito em NC¹ é dado. Sem perda de generalidade , assuma que usa somente portas AND e NOT .

Lema 1 : Se existe um programa de ramificação que às vezes funciona como uma permutação P e Q , por vezes, como , por permutações direito do multiplicador na primeira instrução por α , e na última instrução deixou-se multiplicando por β , podemos fazer um circuito de o mesmo comprimento que se comporta como βPα ou βQα , respectivamente.

Chamar um programa de ramificação α - computar um circuito C se ele funciona como a identidade quando a saída do C é 0, e como α quando a saída do C é 1.

Como consequência do lema 1 e o facto de todos os ciclos de comprimento 5 são conjugado, para quaisquer dois ciclos de 5 α , β , se existe um programa de ramificação α - computável de um circuito C , então existe um programa de ramificação β-computável no circuito de C , com o mesmo comprimento .

Lema 2 : Existem 5-ciclos γ , δ tal que o seu comutador $\gamma \delta \gamma ^{-1}\delta ^{-1}=\epsilon$ é um 5-ciclo. Por exemplo, γ = (1 2 3 4 5 ) , δ = ( 1 3 5 4 2).

Vamos agora provar o teorema de Barrington por indução.

Suponhamos que, para todos os subcircuitos D de C e 5-ciclos α , existe um programa de ramificação α-computável C. Iremos demonstrar que para todos os 5-ciclos α , existe um programa de ramificação α-computável C.

• Se o circuito gera x_i , o programa de ramificação tem uma instrução de controle x_i e saída identidade ou α respectivamente.
• Se as saídas do circuito $\neg C$ , onde C é um circuito diferente. Crie um programa de ramificação $\alpha ^{-1}$-computável C, e multiplicar saída do programa (usando o lema 1) por α para obter um programa de ramificação saída $id$ ou α , ou seja, α -computável $\neg C$.
• Se as saídas do circuito $C\wedge D$, junta-se aos programas de ramificação que $\delta ^{-1}$-compute D, $\gamma ^{-1}$-compute C, δ-compute D, γ-compute C. Se um dos circuitos de saída 0, o programa resultante será de identidade , se ambos os circuitos de saída 1 , o programa resultante funcionará como ε . Em outras palavras , temos um programa de computação ε $C\wedge D$. Porque ε e α são dois 5-ciclos , são conjugados , e existe um programa α -computável $C\wedge D$.

O tamanho do programa de ramificação é , no máximo, $4^{d}$, em que d é a profundidade do circuito. Se o circuito tem profundidade logarítmica , o programa de ramificação tem comprimento polinomial.

Bibliografia

• Arora, Sanjeev; Barak, Boaz (2009). Computational complexity. A modern approach. [S.l.]: Cambridge University Press. ISBN 978-0-521-42426-4. Zbl 1193.68112 
• Clote, Peter; Kranakis, Evangelos (2002). Boolean functions and computation models. Col: Texts in Theoretical Computer Science. An EATCS Series. Berlin: Springer-Verlag. ISBN 3-540-59436-1. Zbl 1016.94046 
• Greenlaw, Raymond, James Hoover, and Walter Ruzzo. Limits To Parallel computation; P-Completeness Theory. ISBN 0-19-508591-4
• Kozen, Dexter C. (1992). The design and analysis of algorithms. [S.l.: s.n.]  Lectures 28 - 34 and 36
• Kozen, Dexter C. (2006). Theory of Computation. Col: Texts in Computer Science. [S.l.]: Springer-Verlag. ISBN 1-84628-297-7. Zbl 1102.68025  Lecture 12: Relation of NC to Time-Space Classes
• Papadimitriou, Christos (1993). «Section 15.3: The class NC». Computational Complexity 1st ed. [S.l.]: Addison Wesley. pp. 375–381. ISBN 0-201-53082-1 
• Straubing, Howard (1994). Finite automata, formal logic, and circuit complexity. Col: Progress in Theoretical Computer Science. Basel: Birkhäuser. ISBN 3-7643-3719-2. Zbl 0816.68086 
• Vollmer, Heribert (1998). Introduction to circuit complexity. A uniform approach. Col: Texts in Theoretical Computer Science. Berlin: Springer-Verlag. ISBN 3-540-64310-9. Zbl 0931.68055