Re La To Rio

Computa¸ca˜o Paralela e a Classe N C Daniel Saad Nogueira Nunes 06/81792 29 de novembro de 2009 Resumo Esse documento visa apresentar aspectos introdut´ orios da teoria de complexidade da computa¸ca ˜o paralela bem como modelos computacionais razo´ aveis e uma discuss˜ ao acerca da quest˜ ao da P-Completude e a classe de complexidade N C

1

Sum´ ario 1 Introdu¸ c˜ ao 1.1 Multiplica¸c˜ ao de Matrizes Quadradas . . . . . . . . . . . . . . . . 1.2 Menor Caminho Entre Qualquer Par de V´ertices . . . . . . . . . 1.3 Princ´ıpio de Brent . . . . . . . . . . . . . . . . . . . . . . . . . .

3 3 4 6

2 Modelos Computacionais 2.1 Modelo PRAM . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.2 Modelo de Circuitos Booleanos . . . . . . . . . . . . . . . . . . .

7 7 8

3 Complexidade Computacional 3.1 Classe N C . . . . . . . . . . . . . . . . . . . 3.2 Redu¸c˜ ao . . . . . . . . . . . . . . . . . . . . 3.2.1 Redu¸c˜ ao Many-One . . . . . . . . . 3.2.2 Redu¸c˜ ao do tipo Turing . . . . . . . 3.2.3 P-Completude . . . . . . . . . . . . 3.3 Rela¸c˜ ao Tempo-Espa¸co . . . . . . . . . . . . 3.3.1 Parallel Computation Thesis (PCT) 3.4 Problemas Inerentemente Sequenciais . . . . 3.4.1 Problema P-Completo Gen´erico . . . 3.4.2 Circuit Value Problem (CVP) . . . .

2

. . . . . . . . . .

. . . . . . . . . .

. . . . . . . . . .

. . . . . . . . . .

. . . . . . . . . .

. . . . . . . . . .

. . . . . . . . . .

. . . . . . . . . .

. . . . . . . . . .

. . . . . . . . . .

. . . . . . . . . .

. . . . . . . . . .

10 10 10 10 11 11 11 12 12 12 12

1

Introdu¸ c˜ ao

A essˆencia da computa¸c˜ ao paralela est´a na busca de se obter um menor tempo entre o come¸co e o fim da computa¸c˜ao de algum problema. Comparado com algum modelo sequencial de computa¸c˜ao isso parece o tanto quanto ´obvio, mas a computa¸c˜ ao paralela ´e bem mais do que tentar obter uma simples diminui¸c˜ao do tempo necess´ ario para resolver algum problema sequencial, o grande interesse do estudo da complexidade computacional paralela, est´a em obter uma diminui¸c˜ ao exponencial do tempo necess´ario para resolver esse mesmo problema e reconhecer os limites da mesma. Por exemplo, seja A1 um algoritmo que resolve um problema sequencial em O(n), suponha que um algoritmo A2 foi projetado para resolver o mesmo problema, s´ o que esse algoritmo foi projetado para um modelo de computa¸c˜ao paralelo, e resolve esse problema em O(n) tamb´em, poss´ıvelmente o algoritmo A2 ser´ a mais r´ apido que o algoritmo A1 quanto ao tempo de execu¸c˜ao, no entando n˜ ao ser´ a assintoticamente mais r´apido, o tempo para resolver o problema continua linear na ordem de entrada. Um resultado mais interessante seria o projeto de um terceiro algoritmo A3 que resolve o mesmo problema tamb´em em algum modelo computacional paralelo, mas que leva da ordem de O((log(n))O(1) ) no tamanho n da entrada, isso iria refletir numa diminui¸c˜ ao exponencial na quantidade de passos necess´arios, em termos assintoticos, para resolver o mesmo problema. Esse ´e o tipo de resultado em que o estudo da computa¸c˜ao paralela almeja alcan¸car.

1.1

Multiplica¸c˜ ao de Matrizes Quadradas

Para ilustrar o projeto de algoritmos paralelos tome o problema da multiplica¸c˜ao de matrizes quadradas .Esse problema consiste em multiplicar uma matriz A ∈ Rnxn por uma matriz B ∈ Rnxn resultando em uma matriz C ∈ Rnxn . Um algoritmo sequencial conhecido resolve esse problema em Θ(n3 ), para isso ele toma cada elemento ci,j da matriz C e o coloca dependente do seguinte produto escalar. ci,j =

n X

ai,k · bj,k

(1)

k=1

Esse algoritmo ´e claramente da ordem de Θ(n3 ) visto que existem n2 produtos escalares, e cada produto escalar leva da ordem de Θ(n) para realizar o seu trabalho. Assintoticamente existem algoritmos melhores como o algoritmo de Strassen O(nlog2 7 ), mas o exemplo ser´a dado no algoritmo inicialmente apresentado. O poss´ıvel projeto de um algoritmo paralelo para resolver o mesmo problema [4], ´e tomar n3 processadores, cada processador fica respons´avel por produzir o resultado de um produto ai,k · bj,k . Nesse ponto todos os produtos foram resolvidos em O(1). Mas ainda ´e necess´ario fazer o somat´orio dos produtos para cada elemento ci,j . Um algoritmo ingˆenuo para fazer isso ´e tomar n2 dos processadores e alocar um para cada somat´orio. Pi,j,1 =

n X k=1

3

ai,k · bj,k

(2)

Dessa forma esse algoritmo de multiplica¸c˜ao de matrizes leva Θ(n) passos ´ um resultado bom se comparado paralelos, usando de Θ(n3 ) processadores. E com o algoritmo sequencial que levava Θ(n3 ), mas n˜ao ´e uma redu¸c˜ao exponencial do tempo no tamanho da entrada. Para obter tal redu¸c˜ao ´e necess´ario somar os produtos de uma maneira esperta. Tal maneira esperta pode ser feita usando uma ´arvore de adi¸c˜oes, desse modo a soma levar´ a log n + 1 passos paralelos para a execu¸c˜ao. Deixando assim o algoritmo de multiplica¸c˜ ao de matrizes levando Θ(log n) passos paralelos para computar o problema da multiplica¸c˜ao de matrizes quadradas, um decaimento exponencial se compararmos com a cota antiga de Θ(n).

P0

+

P3

P1

P2

+

.. . P4

... .. .

´ Figura 1: Arvore de adi¸c˜oes entre os processadores

1.2

Menor Caminho Entre Qualquer Par de V´ ertices

O problema de encontrar o menor caminho entre quaisquer par de v´ertices de um grafo, G = (V, E) tal que |V | = n, est´a em P, o algoritmo de Floyd-Warshall resolve o problema em O(|V |3 ) usando de programa¸c˜ao dinˆamica. Uma outra abordagem pode ser feita para resolver o mesmo problema de maneira eficiente em paralelo a partir de uma id´eia sequencial de uma maneira indutiva [9]. (m)

Defini¸ c˜ ao 1.2.1 Seja li,j o custo do caminho de menor peso que leva o v´ertice i ao v´ertice j, m representa que esse caminho cont´em no m´ aximo m elos. O caso base ´e quando m = 0, o custo de um v´ertice i para ele mesmo ´e 0, j´ a o custo de um v´ertice i para um v´ertice j, com i 6= j ´e infinito, visto que o caminho tem que ter zero arestas.  0, i = j (0) li,j = (3) ∞, i 6= j 4

(m)

O passo de indu¸c˜ ao consiste que li,j , isto ´e, o caminho de menor custo de i m−1 a j pode ser obtido em fun¸c˜ ao de li,j , pois um sub-caminho de um caminho otimo tem que ser ´ ´ otimo tamb´em, e do peso da aresta dos n´os adjacentes a j que est˜ ao no sub-caminho ´ otimo. Ent˜ao temos o seguinte resultado   (m−1) li,j = min li,k + wk,j (4) 1≤k≤n

Ou seja, o caminho de menor custo de i `a j ´e aquele que minimiza os subcaminhos com m − 1 elos e o peso dos predecessores de i. Representando li,j por uma matriz de adjancˆencias, teremos que o resultado (n−1) de todos os menores caminhos estar˜ao em li,j , visto que um caminho que cont´em v v´ertices tem que ter v − 1 arestas. Mas a substitui¸c˜ ao dos seguintes termos da equa¸c˜ao 4 da seguinte maneira l(m−1) → a w→b l(m) → c min → + +→· Chegaremos na equa¸c˜ ao 1, de multiplica¸c˜ao de matrizes, logo o problema do menor caminho para os pares, pode ser resolvido por sucessivas “multiplica¸c˜oes” de matrizes, onde a opera¸c˜ ao de soma corresponde a opera¸c˜ao min da seguinte maneira: Seja Wi,j a matriz de adjacencias representando o valor da aresta e = {i, j}, ou seja   0, i = j f (e), e = {i, j} , ou seja, o custo da aresta (5) W =  ∞, e = {i, j} ∈ /E E substituindo 0 (identidade da soma),por ∞ (identidade da opera¸c˜ao min) temos: (x)

(x−1)

li,j = li,j

· W,

x ∈ {1, . . . , n − 1} 4

(6)

O que leva um tempo total de Θ(|V | ). (v−1) Mas ´e f´ acil ver que o resultado se encontra apenas em li,j , portanto podemos fazer a “multiplica¸ca˜o” de uma maneira mais r´apida, basta ver que d(log(n−1))e−1 (1) (1) (n−1) Li,j = W , Li,j = W 2 = W · W , . . . , Li,j = W2 . Ou seja, as matrizes s˜ ao obtidas elevando o resultado anterior ao quadrado. Portanto, para obter o resultado, precisamos de apenas dlog(n − 1)e multiplica¸c˜oes de matrizes, fazendo com que o custo para resolver o problema seja reduzido para Θ(n3 log n). Em paralelo, temos que o custo de multiplicar matrizes pode ser obtido com Θ(log n) passos paralelos, portanto, o algoritmo de menores caminhos entre qualquer par de v´ertices leva Θ(log2 n) passos paralelos, usando n3 processadores. O fechamento transitivo de um grafo tamb´em ´e obtido de forma semelhante, apenas por uma troca de opera¸c˜oes tamb´em na multiplica¸c˜ao de matrizes [4]. 5

1.3

Princ´ıpio de Brent

Defini¸ c˜ ao 1.3.1 A quantidade de trabalho W (n) feita por um algoritmo paralelo ´e definido como a soma da quantidade de opera¸co ˜es feitas por todos os processadores durante a computa¸ca ˜o. Como um algoritmo paralelo pode ser simulado com uma m´aquina com p processadores, temos que o tempo necess´ario para execu¸c˜ao do algoritmo em paralelo ´e dada pela seguinte rela¸c˜ao: T (n) ≤ b

W (n) c + S(n) p(n)

(7)

Onde p(n) descreve o n´ umero de processadores em fun¸c˜ao da entrada, e S(n) descreve a quantidade de passos paralelos necess´arios para a execu¸c˜ao do algoritmo e T descreve o tempo necess´ario para a execu¸c˜ao do algoritmo. Portanto ´e poss´ıvel estabelecer uma cota inferior de processadores `a serem usados em determinado , por exemplo, no algoritmo de multiplica¸c˜oes de matrizes o custo total de trabalho foi de Θ(n3 ) visto que temos n2 produtos escalares. Logo para T = O(log n), a cota antiga e analisando 7, precisar´ıamos de n3 no m´ınimo Ω( log n ) processadores, visto que S(n) = O(log n). Al´em disso, pelo mesmo motivo, dizemos que uma m´aquina sequencial pode emular o algoritmo paralelo, portanto: T (n)sequencial ≤ T (n)paralelo × p(n)

(8)

Portanto , se o tempo sequencial for super-polinomial, s´o conseguiremos um tempo paralelo poli-logaritmo se o n´ umero de processadores for superpolinomial, e isso n˜ ao corresponde a um modelo razo´ avel de computa¸c˜ao paralela.

6

2

Modelos Computacionais

Para falar de computa¸c˜ ao paralela e classes computacionais que abrangem os problemas sol´ uveis em paralelo de uma maneira eficiente, ´e necess´ario se basear em algum modelo razo´ avel de computa¸c˜ao. Os modelos, em geral, se diferenciam por dois grandes fatores. O n´ıvel de tratamento de opera¸c˜ oes, isto ´e, um modelo que trate opera¸c˜oes bit a bit como unidade b´ asica de opera¸c˜ao ´e mais rigoroso do que um modelo que trata opera¸c˜ oes de mais alto n´ıvel como exponencia¸c˜ao por exemplo como unidade b´ asica de opera¸c˜ ao. O outro fator ´e como os recursos do modelo computacional paralelo se comunicam, se permitirmos uma comunica¸c˜ao muito poderosa, modelos de computa¸c˜ ao mais relaxados no aspecto comunica¸c˜ao poder˜ao n˜ao conseguir simular o modelo mais poderoso por um fator polinomial.

2.1

Modelo PRAM

O modelo PRAM1 ´e a vers˜ ao paralela do modelo RAM, este modelo abstrai o custo de comunica¸c˜ ao entre os processadores, ou seja, n˜ao se considera uma poss´ıvel topologia em que os processadores se organizam, al´em disso abstrai alguns outros fatores como sincroniza¸c˜ao entre os processadores. Tal modelo fornece uma vis˜ ao de alto n´ıvel, o que facilita a an´alise de algoritmos, o modelo ´e bastante intuitivo e foi usado implicitamente nos algoritmos da multiplica¸c˜ao de matrizes e menor caminho entre quaisquer par de v´ertices, descritos anteriormente. Defini¸ c˜ ao 2.1.1 Uma m´ aquina PRAM ´e uma cole¸c˜ ao de m´ aquinas RAM, cada RAM consiste de uma fita de entrada s´ o de leitura, uma fita de sa´ıda, um n´ umero infinito de c´elulas de mem´ oria. Um programa RAM ´e uma sequˆencia finita de instru¸c˜ oes como LOAD, STORE, ADD, etc . . . A computa¸c˜ ao em uma RAM acaba quando esta encontra a instru¸c˜ ao HALT, uma defini¸ca ˜o mais completa do modelo RAM se encontra em [4],[1],[9]. Como visto, uma PRAM consiste em p processadores RAM. Al´em disso esse modelo possui um conjunto de c´elulas de mem´ oria compartilhada. Defini¸ c˜ ao 2.1.2 A computa¸c˜ ao em uma PRAM ´e feita da seguinte maneira, uma entrada w ∈ Σ? ´e colocada na mem´ oria compartilhada. Inicialmente somente o processador P0 est´ a ativo, e este pode ativar outros processadores. Mas o modelo retringe a quantidade de processadores ativos, isto ´e, n˜ ao podemos ter uma ativa¸c˜ ao de um n´ umero super-polinomial de processadores em um tempo polinomial. Quando o processador P0 encontra a instru¸c˜ ao HALT a computa¸c˜ ao em todos os processadores para,e o resultado da computa¸c˜ ao w0 se encontra tamb´em na mem´ oria compartilhada. Varia¸c˜ oes do modelo PRAM se distinguem quanto ao acesso `a mem´oria compartilhada, dentre elas podemos citar. • CRCW-PRAM2 : Esse modelo permite escrita e leitura simultˆanea de uma c´elula de mem´ oria por diversos processadores RAM. 1 Parallel

Random Access Machine concurrent-write

2 Concurrent-read

7

• CREW-PRAM3 : Esse modelo permite leitura simultˆanea, mas apenas se permite que um processador escreva na c´elula de mem´oria compartilhada. • CROW-PRAM4 : Esse modelo permite leituras simultˆaneas,no mais cada c´elula de mem´ oria compartilhada tem um determinado processador como dono, e s´ o ele pode escrever na mesma. • EREW-PRAM5 : N˜ ao se pode ter 2 ou mais processadores acessando (lendo ou escrevendo) a mesma c´elula de mem´oria compartilhada. Todas essas varia¸c˜ oes s˜ ao polinomialmente equivalentes, isto ´e, se o modelo P1 computa em t(n) o modelo P2 computa em t(n)O(1) , ambos usando um n´ umero polinomial de processadores.

2.2

Modelo de Circuitos Booleanos

O modelo PRAM ´e um bom modelo para analisar algoritmos, pois ele abstrai muitos obst´ aculos como dito anteriormente. No entanto ´e necess´ario, para um estudo mais aprofundado, um modelo um pouco mais pr´oximo da realidade, mais pr´ oximo da implementa¸c˜ao. A n´ıvel de compara¸c˜ ao, para combinar b bits em uma PRAM , ´e poss´ıvel fazer em O(1), no entanto, no modelo de circuitos booleanos, se limitarmos o n´ umero de entradas nas portas l´ogicas em dois, conseguiremos combinar b bits em Ω(log b), temos uma vis˜ ao em um n´ıvel de abstra¸c˜ao mais baixo do que o modelo PRAM forneceu. Defini¸ c˜ ao 2.2.1 Um circuito booleano α ´e definido como um grafo rotulado, direcionado e ac´ıclio. Cada v´ertice do grafo possui um determinado tipo τ ∈ {I, B0 , B1 , B2 }. Um v´ertice v, cujo τ (v) = I e tem grau de entrada ( in-degree) 0 ´e denominado de entrada ( input), um v´ertice cujo grau de sa´ıda ´e zero ( outdegree) ´e chamado de sa´ıda ( output), um v´ertice cujo tipo τ (v) = Bi ´e chamado de porta ( gate) e tem que ter grau de entrada igual a i. [1] Defini¸ c˜ ao 2.2.2 O conjunto de fun¸c˜ oes l´ ogicas que atuam sobre o circuito ´e definido como Bk = {f |f : {0, 1}k → {0, 1}} Defini¸ c˜ ao 2.2.3 A computa¸c˜ ao no modelo de circuitos booleanos segue da seguinte ´ dado uma tupla Tin = (v1 , v2 , . . . , vn ) de entradas e uma tupla de maneira: E 0 sa´ıda Tout = (v10 , v20 , . . . , vm ). Para cada v´ertice vi da tupla Tin ´e atribu´ıdo um valor ν(vi ) = x ∈ {0, 1}. A computa¸c˜ ao ´e dada de tal forma que os valores dos demais v´ertices s˜ ao atribu´ıdos olhando para a fun¸c˜ ao l´ ogica associada ao v´ertice e pelos valores vindos v´ertices que aumentam o grau de entrada do mesmo. O final da computa¸c˜ ao f {0, 1}n → f {0, 1}m se encontra nos valores obtidos nas sa´ıdas do circuito. Defini¸ c˜ ao 2.2.4 O tamanho do circuito α ´e definido pela cardinalidade de v´ertices em α. J´ a a profundidade do circuito α ´e definido como sendo o maior caminho de um v´ertice de entrada ` a um v´ertice de sa´ıda. 3 Concurrent

Read Exclusive Write owner-write 5 Exclusive-read exclusive-write 4 Concurrent-read

8

Portanto um determinado circuito α faz uma computa¸c˜ao de f {0, 1}n `a f {0, 1}m , no entanto isso n˜ ao representa a no¸c˜ao de algoritmo, que tˆem que aceitar um tamanho gen´erico da entrada. Ent˜ao precisamos do conceito de fam´ılia de circuitos. Defini¸ c˜ ao 2.2.5 Uma fam´ılia de circuitos {αn } ´e uma cole¸c˜ ao de circuitos αi , cada um computando a fun¸c˜ ao f i : {0, 1}i → {0, 1}m(i) . Descrever uma fun¸c˜ ao de circuitos requer uma aten¸c˜ao especial, pois se n˜ao for colocada alguma restri¸c˜ ao, tal cole¸c˜ao pode “computar” fun¸c˜oes n˜ao comput´ aveis [1], ent˜ ao devemos restringir o poder de constru¸c˜ao de circuitos, isto ´e, a constru¸c˜ ao de um descri¸ca˜o de circuitos, feita por um determinado modelo, n˜ ao pode ter mais poder computacional do que esse mesmo modelo. Por exemplo, se a descri¸c˜ ao de uma fam´ılia de circuitos for constru´ıdo por uma m´ aquina de Turing Mt que se limita a usar O(log n) de espa¸co no tamanho da entrada, a fam´ılia descrita n˜ao ter´a mais poder computacional que a m´aquina Mt . Informalmente isso corresponde ao conceito de uniformidade introduzido por Allan Borodin [11]. Portanto ajustando diferentes construtores de poderes diferentes, poderemos criar descri¸c˜ oes das fam´ılias com poder computacional diferente.

9

3 3.1

Complexidade Computacional Classe N C

A classe dos problemas N C ´e a classe dos problemas que podem ser resolvidos em tempo polilogaritmo (log n)O(1) usando um n´ umero polinomial de processadores nO(1) no modelo PRAM. A classe N C tamb´em pode ser definida como as linguagens decid´ıveis por um circuito booleano de profundidade (log n)O(1) e de tamanho nO(1) . Defini¸ c˜ ao 3.1.1 A classe N C ´e expressa como a uni˜ ao das classes N C k , k ∈ N, ou seja [ NC = N Ck (9) k∈N

O modelo de circuitos booleanos ´e mais robusto quanto `as sub-classes N C k do que o modelo PRAM, isto ´e, para determinado valor de k a subclasse N C k pode ser diferente em varia¸c˜ oes do modelo PRAM. Defini¸ c˜ ao 3.1.2 As sub-classes de complexidade computacional N C k s˜ ao definidas como o conjunto de linguagens aceitas por uma fam´ılia de circuitos booleano de profundidade O(logk n) e tamanho nO(1) . Informalmente N C ´e a classe dos problemas que possuem uma solu¸c˜ao eficiente (assintoticamente) em paralelo.

3.2

Redu¸c˜ ao

Defini¸ c˜ ao 3.2.1 Uma redu¸c˜ ao ´e um meio de converter um determinado problema A ` a outro determinado problema B de forma que se a solu¸c˜ ao do problema B for conhecida, podemos us´ a-la para resolver o problema A. A redu¸c˜ ao entre problemas pode ser usada para explorar a complexidade envolvendo os mesmos problemas e tamb´em explorar a diferen¸ca entre classes de complexidade computacional. 3.2.1

Redu¸ c˜ ao Many-One

A redu¸c˜ ao Many-One ´e uma forma de mapear um problema A em outro problema B de tal forma que ao resolver B conseguimos obter a resposta para A, formalmente isso seria equivalente `a seguinte defini¸c˜ao. Defini¸ c˜ ao 3.2.2 Uma fun¸c˜ ao f : Σ? → Σ? ´e uma fun¸c˜ ao comput´ avel se existe uma m´ aquina de Turing Mt = (Q, Σ, Γ, δ, q0 , F ⊆ Q) que para cada entrada w ∈ Σ? , a m´ aquina p´ ara com f (w) escrita na fita. Defini¸ c˜ ao 3.2.3 Dada duas linguagens A e B, dizemos que A se reduz a B se existe uma fun¸c˜ ao comput´ avel f : Σ? → Σ? de tal forma que, ∀w ∈ Σ? , w ∈ A ⇔ f (w) ∈ B [10]. Defini¸ c˜ ao 3.2.4 Caso A se reduza ` a B pela redu¸c˜ ao Many-One, representamos por A ≤m B.

10

f : Σ ? → Σ?

A

B

Figura 2: Redu¸c˜ao Many-One entre problemas 3.2.2

Redu¸ c˜ ao do tipo Turing

3.2.3

P-Completude

Teorema 3.2.1 Tanto a redu¸ca ˜o do tipo Turing quando a redu¸c˜ ao many-one s˜ ao fechadas nas classes P e N C [1]. Defini¸ c˜ ao 3.2.5 Seja C uma classe de complexidade. Dizemos que L ´e Ccompleta se qualquer L0 ∈ C se reduz a L e L ∈ C [4]. Segundo a defini¸c˜ ao 3.2.5 ´e f´acil ver que: Defini¸ c˜ ao 3.2.6 Seja L ∈ P, L ´e P-completa se, e somente se toda linguagem L0 ∈ P se reduz ` a L.

3.3

Rela¸c˜ ao Tempo-Espa¸co

O primeiro problema P-completo, Path Systems, foi anunciado por Cook [8]. A motiva¸c˜ ao era responder se uma m´aquina de turing que decide em tempo polinomial conseguiria decidir usando (log n)O(1) c´elulas de mem´oria, ou seja, a motiva¸c˜ ao para estudar os problemas P-completos surgiu muito antes com o estudo do espa¸co polilogar´ıtimico do que com os conceitos de tempo paralelo. Para tentar responder tal quest˜ao, se utilizava de uma t´ecnica de redu¸c˜ao espacial, de tal forma que a fun¸c˜ao de redu¸c˜ao n˜ao levava mais de SP ACE(log n) para fazer a transforma¸c˜ ao. N˜ ao se sabe dizer tamb´em se a classe dos problemas que est˜ao em P podem ser sol´ uveis usando O(log n) c´elulas de espa¸co (classe L). Para ilustrar a situa¸c˜ao entre espa¸co e tempo temos o seguinte teorema. Teorema 3.3.1 Reachability Method Para uma fun¸c˜ ao f(n) adequada: I) SP ACE(f (n)) ⊆ N SP ACE(f (n)) II) T IM E(f (n)) ⊆ N T IM E(f (n)) III) N T IM E(f (n)) ⊆ SP ACE(f (n)) IV ) N SP ACE(f (n)) ⊆ T IM E(k log n+f (n) )

11

Do teorema 3.3.1 temos o seguinte resultado. N C1 ⊆ L ⊆ N L ⊆ N C2 ⊆ N C ⊆ P A demonstra¸c˜ ao da primeira e terceira inclus˜ao se encontra em [4]. Portanto, de fato se tivermos que o resultado L = P, teremos tamb´em que N C = P. 3.3.1

3.4

Parallel Computation Thesis (PCT)

Problemas Inerentemente Sequenciais

O termo inerentemente sequˆencial surgiu do trabalho de John Reif [5], tal termo remete aos problemas d´ıficeis de paralelizar eficientemente. Formalmente podemos definir que um determinado problema ´e inerentemente sequencial caso n˜ao se conheca uma solu¸c˜ ao para o mesmo que esteja em N C. Os problemas P-completos capturam a dificuldade dos problemas da classe P visto que, se algum problema P tenha solu¸c˜ao em N C ent˜ao todos os problemas de P est˜ ao em N C. Ou ent˜ ao, se mostrarmos que um problema P-completo n˜ao pode ser solucionado de uma maneira eficiente em paralelo, estaremos mostrando que P 6= N C. Portanto analisar os problemas P-completos ´e um caminho para ? responder a quest˜ ao P = N C. 3.4.1

Problema P-Completo Gen´ erico

3.4.2

Circuit Value Problem (CVP)

12

Referˆ encias [1] Limits to Parallel Computation: P-Completeness Theory RAYMOND GREENWLAW, H. JAMES HOOVER, WALTER L. RUZZO [2] Introduction to Automata Theory, Languages, and Computation JOHN E. HOPCROFT, RAJEEV MOTWANI, JEFFREY D. ULLMAN [3] Parallel Complexity Theory IAN PARBERRY [4] Computacional Complexity CHRISTOS H. PAPADIMITRIOU [5] Depth-First Search Is Inherently Sequential JOHN H. REIF [6] Parallel Computing PRAM algorithms SIDDHARTHA CHATTERJEE, JAN PRINS [7] Modelo Computacional e Redu¸ c˜ ao Entre Problmas PEDRO J. DE REZENDE [8] An observation on time-storage trade off S. A. COOK [9] Introduction to Algorithms THOMAS H. CORMEN, CHARLES E. LEISERSON, RONALD L. RIVEST, CLIFFORD STEIN [10] Introduction To The Theory Of Computation MICHAEL SIPSER [11] On Relating Time And Space To Size and Depth ALLAN BORODIN

13