not available

Nos 4 primeiros capitulos do trabalho, estudamos a complexidade computacional do reconhecimento de propriedades de grafos invariantes por isoformismos. Estudamos o problema para propriedades monotonicas nao-triviais de grafos. Sabe-se atualmente que a complexidade deterministica de pior caso dessas propriedades e 'OMEGA' ('N POT.2'), onde n e o numero de vertices dos grafos considerados. Existe entretanto uma conjectura de yao e karp de 1977 que diz que a complexidade aleatoria destas propriedades e tambem 'OMEGA' ('N POT.2'). Os resultados de yao e king sobre esta conjectura e o melhor limite inferior conhecido atualmente de 'OMEGA' ('N POT.4/3'), provado recentemente por p. Hajnal. Caso a conjectura de yao e karp venha a ser provada, pode-se por em duvida a eficacia de metodos probabilisticos aplicados a problemas computacionais. No ultimo capitulo apresentamos resultados de valiant e reischuk que comprovam que no caso do problema de selecao em paralelo do menor elemento de um conjunto, existe um algoritmo aleatorio que e assintoticamente mais eficiente do que qualquer algoritmo deterministico. Neste mesmo capitulo, apresentamos um resultado de alon e azar que prova que no caso de ordenacao de conjuntos com n elementos, usando algoritmos que utilizam mais de n processadores, a eficiencia de algoritmos aleatorios nao e melhor do que a de algoritmos deterministicosnot availabl