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).