MAC 828 Tópicos em Complexidade Computacional

• A.V. Aho, J.E. Hopcroft, and J.D. Ullman, The design and analysis of computer algorithms, Addison-Wesley, Reading, Mass., 1974.
• S. Arora , Probabilistic checking of proofs and hardness of approximation problems , Ph.D. Thesis.
• S. Arora , Around the PCPO theorem , Lecture Notes, 58 pages.
• S. Arora and C. Lund , Hardness of Approximations , Chapter in the book Approximation Algorithms for NP-hard problems, ( D. Hochbaum editor). [A survey which includes proofs of the basic non-approximability applications. Original place of source ]
• S. Arora and C. Lund , R. Motwani, M. Sudan, and M. Szegedy, Proof verification and the hardness of approximation problems , 25 pages [Este é o artigo originalque prova que PCP(log n,1)=NP].
• L. Babai, Transparent Proofs and Limits to Approximation , 61 pages.
  
  • Proceedings of the 1st European Congress Math., 1994
  • Survey paper on transparent proofs and their impact to approximability results
  • Contents
• J.L. Balcázar, J. Diaz, J. Gabarró, Structural Complexity, vol. I, Springer-Verlag, Berlin, 1988.
• T. Behrendt and K. Compton, Optimization problems: expressibility, approximation properties and expected asymptotic growth of optimal solutions , 25 pages.
• M. Bellare , O. Goldreich, and M. Sudan, Free bits, PCPs and non-approximability --- towards tight results , 114 pages.
• J. Cai and A. Condom, PSPACE is provable by two provers in one round , 12 pages.
• T.H. Cormen, C.E. Leiserson, and R.L. Rivest, Introduction to algorithms, The MIT Press, McGraw-Hill Book Company, 1990, QA758 C811i.
• P. Crescensi and L. Trevisan On approximation scheme preserving reducibility and its applications, 12 pages.
• P. Crescensi and L. Trevisan On approximation scheme preserving reducibility and its applications, 14 pages (quase igual ao anterior).
• M.R. Garey and D.S. Johnson, Computers and intractability: A guide to the theory of NP-completeness, Freman, New York, 1979.
• O. Goldreich, Probabilistic Proofs system --- a survey , 19 pages.
• J. Hastad, Complexity Theory , Lecture Notes, 130 pages.
• J.E. Hopcroft, and J.D. Ullman, Introduction to automata theory, languages, and Computation, Addison-Wesley, Reading, Mass., 1979.
• S. Khanna, R. Motwani, M. Sudan, and U. Vazirani, On syntatic versus computational views of approximation , 25 pages.
• Y. Kohayakawa and J.A.R. Soares, Demonstrações Transparentes e a impossibilidade de aproximações. 20o. Colóquio Brasileiro de Matemática. IMPA, Instituto de Matemática Pura e Aplicada, Rio de Janeiro, julho 1995. x+107pp.
• H.R. Lewis and C.H. Papadimitriou , Elements of the theory of computation , Prentice-Hall, Englewood Cliffs, NJ, 1981.
• L. Lovász , Computational complexity , Lecture Notes, March 15, 1994, 147 pages [translation by Peter Gács]
• M. Luby and A. Wigderson, Pairwise independence and derandomization [ Original place of source]
• C. Lund , L. Fortnow, H. Karloff and N Nisam Algebraic Methods for Interactive proof systems , 10 pages.
• S. Hougardy , H.-J. Prömel , and A. Steger , Probabilistic checkale proofs and their consequence to approximation algorithms , 48 pages [Reescrita da prova PCP(log n,1)=NP e provas de inaproximabilidade].
• C.H. Papadimitriou , Computational complexity, Addison-Wesley, Reading, Mass. 1994.
• C.H. Papadimitriou , NP-completeness: A retrospective , 5 pages.
• A. Selman, Average time complexity classes , 20 pages.
• Chee K. Yap, Introduction to Complexity Classes , Oxford University Press, (to appear).