Tese

Uma introdução técnica relativa às provas robustas checáveis probabilisticamente (1997)

• Authors:
  • Matsushigue, Claus Akira
  • Bianconi, Ricardo (Orientador)
• Autor USP: MATSUSHIGUE, CLAUS AKIRA - IME
• Unidade: IME
• Sigla do Departamento: MAP
• Subjects: MATEMÁTICA APLICADA; COMPUTABILIDADE E COMPLEXIDADE
• Agências de fomento:
  • Coordenação de Aperfeiçoamento de Pessoal de Nível Superior (CAPES)
• Language: Português
• Abstract: Na última década, vários tipos de sistemas de provas probabilísticas mostraram ter papel decisivo no desenvolvimento da Teoria da Ciência da Computação. Isto pode ser verificado pelo grande número de estudos acerca das provas interativas, provascom conhecimento-zero e provas transparentes (ou holográficas). Estes tópicos se norteiam pela robustez das codificações e pela capacidade computacional em checá-las. Buscamos, no texto, trazer uma introdução técnica relativa às provas robustaschecáveis probabilisticamente. Neste enfoque, a nova caracterização da classe não-determinística de tempo polinomial pela classe das Provas Checáveis Probabilisticamente formulada por Arora, Lund, Motwani, sudan e Szegedy em [ALM+92], NP =PCP(log n,1), é de importância central. Pretendemos provar tal caracterização, visto que ela perpassa os principais pontos do assunto e, ainda, abrange subjacentemente um grande ferramental computacional, algébrico e probabilístico, que éfundamental neste tópico. O teorema NP = PCP(log n, 1), tem no seu bojo a surpreendente propriedade que problemas de decisão em NP podem ser resolvidos por Máquinas de Turing de tempo polinomial no comprimento da entrada, se obtiverem ajuda deuma prova robusta (portanto, uma máquina não-determinística) e se puderem lançar moedas "justas" (uma máquina probabilística). Entretanto, estas máquinas são restritas a só poderem ler um número logarítmico no comprimento da entrada de letras daprova robusta,sorteadas por um número constante de bits aleatórios, e têm uma probabilidade constante, e tão pequena quanto se queira, de aceitarem "erradamente" uma entrada. Tendo como base o referido teorema, ou utilizando-se as suastécnicas, pode-se obter diversos resultados de inaproximabilidade de soluções ótimas. Assim, o texto também fornece um exemplo simples do uso das provas robustas checáveis probabilisticamente. Com ele, na Otimização Combinatória sabe-se ) hoje que os problemas MAX-SNP-difíceis não estão em PTAS ou, em outras palavras, não se pode obter a solução ótima, a menos de uma fração constante qualquer, com algoritmos de tempo polinomial, supondo-se P'DIFERENTE' NP
• Imprenta:
  • Publisher place: São Paulo
  • Date published: 1997
• Data da defesa: 10.07.1997


---

How to cite

A citação é gerada automaticamente e pode não estar totalmente de acordo com as normas

• ABNT

  MATSUSHIGUE, Claus Akira. Uma introdução técnica relativa às provas robustas checáveis probabilisticamente. 1997. Dissertação (Mestrado) – Universidade de São Paulo, São Paulo, 1997. Disponível em: https://teses.usp.br/teses/disponiveis/45/45132/tde-20210729-014911/. Acesso em: 23 abr. 2024.

• APA

  Matsushigue, C. A. (1997). Uma introdução técnica relativa às provas robustas checáveis probabilisticamente (Dissertação (Mestrado). Universidade de São Paulo, São Paulo. Recuperado de https://teses.usp.br/teses/disponiveis/45/45132/tde-20210729-014911/

• NLM

  Matsushigue CA. Uma introdução técnica relativa às provas robustas checáveis probabilisticamente [Internet]. 1997 ;[citado 2024 abr. 23 ] Available from: https://teses.usp.br/teses/disponiveis/45/45132/tde-20210729-014911/

• Vancouver

  Matsushigue CA. Uma introdução técnica relativa às provas robustas checáveis probabilisticamente [Internet]. 1997 ;[citado 2024 abr. 23 ] Available from: https://teses.usp.br/teses/disponiveis/45/45132/tde-20210729-014911/

Últimas obras dos mesmos autores vinculados com a USP cadastradas na BDPI:

• Indução de indemonstrabilidades e independências em Complexidade Computacional