Pseudoaleatoriedade em combinatoria e em teoria da computacao.

• Processo: 04/11501-1
• Modalidade de apoio: Bolsas no Brasil - Mestrado
• Data de Início da vigência: 01 de março de 2005
• Data de Término da vigência: 28 de fevereiro de 2007
• Área de conhecimento: Ciências Exatas e da Terra - Ciência da Computação - Matemática da Computação
• Pesquisador responsável: Yoshiharu Kohayakawa
• Beneficiário: Domingos Dellamonica Junior
• Instituição Sede: Instituto de Matemática e Estatística (IME). Universidade de São Paulo (USP). São Paulo , SP, Brasil
• Vinculado ao auxílio: 03/09925-5 - Fundamentos da ciência da computação: algoritmos combinatórios e estruturas discretas, AP.PRNX.TEM
• Assunto(s): Combinatória Pseudoaleatoriedade Complexidade computacional
• Palavra(s)-Chave do Pesquisador: Algoritmos Probabilisticos | Combinatoria | Complexidade Computacional | Desaleatorizacao | Pseudoaleatoriedade

Resumo

Um tópico de bastante interesse em várias áreas da matemática e da teoria da computação refere-se à noção de objetos "típicos" ou "pseudoaleatórios". Por exemplo, em alguns contextos específicos, é possível de se provar que algoritmos probabilísticos são mais "poderosos" que algoritmos determínísticos. Entretanto, um dos problemas fundamentais da área da teoria da complexidade é decidir se máquinas de Turing probabilísticas são efetivamente mais poderosas que as máquinas determinísticas usuais. Este ponto está longe de ser esclarecido. Um resultado clássico que limita o poder computacional de processos aleatórios, devido a Sipser, é que BPP está contida em \Sigma_2. Muito grosseiramente falando, a prova desse resultado é baseada na construtibilidade (de forma eficiente) de conjuntos determinísticos pequenos pseudoaleatórios, que "têm o poder de simular" espaços de probabilidade maiores (de tamanho exponencial na entrada x do problema de decisão "x\in L?"). Neste projeto de mestrado, estamos interessados na investigação de estruturas discretas típicas e na construtibilidade eficiente das mesmas, tendo em vistas aplicações em combinatória e em teoria da computação. Especial ênfase será colocada em aspectos de "cross-fertilization" entre as áreas de combinatória e complexidade computacional. As técnicas envolvidas neste projeto vêm da "combinatória pura", probabilidade, álgebra, e teoria aditiva dos números. (AU)

Publicações acadêmicas

(Referências obtidas automaticamente das Instituições de Ensino e Pesquisa do Estado de São Paulo)

DELLAMONICA JUNIOR, Domingos. Extração de aleatoriedade a partir de fontes defeituosas. 2007. Dissertação de Mestrado - Universidade de São Paulo (USP). Instituto de Matemática e Estatística (IME/SBI) São Paulo.