Complexidade aleatoria de problemas computacionais

Detalhes bibliográficos
Ano de defesa: 1992
Autor(a) principal: Miyamoto, Edson Tadashi
Orientador(a): Não Informado pela instituição
Banca de defesa: Não Informado pela instituição
Tipo de documento: Dissertação
Tipo de acesso: Acesso aberto
Idioma: por
Instituição de defesa: Biblioteca Digitais de Teses e Dissertações da USP
Programa de Pós-Graduação: Não Informado pela instituição
Departamento: Não Informado pela instituição
País: Não Informado pela instituição
Palavras-chave em Português:
Link de acesso: https://teses.usp.br/teses/disponiveis/45/45132/tde-20210729-003347/
Resumo: 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 deterministicos