Studentsky logicky seminar

Literatura k tematu "NP vyhledavaci problemy" (podzim 2010):

Texty (postupne budu doplnovat):

  • P. Beame, S. Cook, J. Edmonds, R. Impagliazzo, and T. Pitassi, The relative complexity of NP search problems, Proc. of the 27th annual ACM symposium on Theory of computing, (May 29-June 01, 1995, Las Vegas) pp.303-314, (1995).

  • J. Buresh-Oppenheim and T. Morioka, Relativized NP Search Problems and Propositional Proof Complexity , in Proceedings of the 19th IEEE Conference on Computational Complexity (CCC), June 2004, pp. 54-67

  • S.Buss and J.Krajicek, An application of boolean complexity to separation problems in bounded arithmetic, Proc.London Math.Soc., 69(3), (1994), pp.1-21. (sekce 5)

  • M. Chiari and J. Krajicek, Witnessing functions in bounded arithmetic and search problems, J. of Symbolic Logic, 63(3), (1998), pp. 1095-1115.

  • D. S. Johnson, C. H. Papadimitriou, and M. Yannakakis, How Easy is Local Search?, J. of Computer and System Sciences 37, pp.79-100, (1988). (extended abstract)

  • J.Hanika, Search problems and bounded arithmetic, PhD Thesis, CUNI, 2004.

  • J. Krajicek, Structured pigeonhole principle, search problems and hard tautologies, J.Symbolic Logic, 70(2), 2005, str.619-630. (sekce 4)

  • J. Krajicek, A. Skelley, and N. Thapen, NP search problems in low fragments of bounded arithmetic , J. of Symbolic Logic, 72(2), (2007), pp. 649-672.

  • N. Megiddo and C.H. Papadimitriou, "A note on total functions, existence theorems and complexity," Theoretical Computer Science 81, pp.317–324, (1991).

  • C.Papadimitriou, "The complexity of the parity argument and other inefficient proofs of existence" , 31st IEEE conference on foundations of computer science (Oct. 22–24, 1990), pp.498-532, (1991).

  • C.Papadimitriou, NP completeness: A restrospective, ICALP 97.

  • C. H. Papadimitriou, A. A. Schäffer, and M. Yannakakis On the complexity of local search , Proc. of the 22nd annual ACM symposium on Theory of computing, pp.438-445, (1990).

  • A. A. Schäffer and M. Yannakakis, Simple local search problems that are hard to solve, SIAM Journal on Computing, Vol.20(1), pp.56-87, (1991).