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

Various types of systems of probabilistic proofs have played a decisive role in the development of Computer Science Theory in the last decade. This can be verified through the great number of studies about interactive proofs, zero-knowledgeproofs, and transparent (or holographic) proofs. These topics are guided by the robustness of the codifications and by the computational capacity of checking them. In this text, we aim at presenting a tecnical introduction relative to theprobabilistically checkable robust proofs. Within this approach, the new characterization of the non-deterministic polynomial-time class through the Probabilistically Checkable Proofs class formulated by Arora, Lund, Motwani, Sudan e Szegedy in[ALM+92], NP = PCP(log n, 1), is of central importance. We intend to pove this characterization, because it encompasses the principal points of the subject and, furthermore, covers subjacently a wide set of computational. algebraic, andprobabilistic tools, which are fundamental in this topic. The theorem NP = PCP9lon n, 1) contains the surprising property that problems of decision in NP may be solved by Turing Machines with polynomial-time in the input length, if they arehelped by a robust proof (therefore, a non-deterministic machine) and can toss 'honest' coins (a probabilistic machine). However, these machines are restricted to read only a logarithmic number in the input length of letters of the robustproofs, drawn like a constant number of random bits, and to have a constant, and as low as wanted, probability of accepting 'wrongly' an input. Taking as basis the referred theorem, or using its techniques, several results of theinapproximability of optimal solutions may be obtained. thus, the text also presents a simple example of the use of the probabilistically checkable robust proofs. With it, in Combinatorial Optimization it now known that problems MAX-SNP-hard arenot in PTAS or, ) in other words, it is impossible to obtain the optimal solution, within a whatsoever constant fraction, in polynomial-time algorithms, supposing P 'DIFERENTE' NP