Computational complexity

Mostrar otras versiones (1)

Guardado en:

Detalles Bibliográficos
Autor principal:	Papadimitriou, Christos H.
Formato:	Libro
Lenguaje:	Inglés
Publicado:	Reading, MA : Addison-Wesley, 1994, reimpr. 1995
Materias:	LOGICA COMPUTACIONAL TEORIA DE LA COMPUTABILIDAD CRIPTOGRAFIA ALGORITMOS COMPLEJIDAD DE PROBLEMAS MAQUINAS TURING
Aporte de:	Registro referencial: Solicitar el recurso aquí Biblioteca Central Dr. Luis F. Leloir (FCEN) de Universidad de Buenos Aires

Tabla de Contenidos:

1 Problems and Algorithms
2 Turing machines
3 Computability
4 Boolean logic
5 First-order logic
6 Undecidability in logic
7 Relations between complexity classes
8 Reductions and completeness
9 NP-complete problems
10 coNP and function problems
11 Randomized computation
12 Cryptography
13 Approximability
14 On P vs. NP
15 Parallel computation
16 Logarithmic space
17 The polynomial hierarchy
18 Computation that counts
19 Polynomial space
20 A glimpse beyond
Index
Author index