Catálogo de publicaciones - libros

Compartir en
redes sociales

Complexity Theory: Exploring the Limits of Efficient Algorithms

Ingo Wegener

Resumen/Descripción – provisto por la editorial

No disponible.

Palabras clave – provistas por la editorial

Programming Techniques; Algorithm Analysis and Problem Complexity; Coding and Information Theory; Logics and Meanings of Programs; Mathematical Logic and Formal Languages; Algorithms

Disponibilidad

Institución detectada	Año de publicación	Navegá	Descargá	Solicitá
No detectada	2005	SpringerLink

Información

Tipo de recurso:

libros

ISBN impreso

978-3-540-21045-0

ISBN electrónico

978-3-540-27477-3

Editor responsable

Springer Nature

País de edición

Reino Unido

Fecha de publicación

2005

Información sobre derechos de publicación

Cobertura temática

Ciencias de la computación e información

Lenguas y literatura

Tabla de contenidos

Verificá que desde tu institución tengas acceso para descargar o solicitar el libro completo o alguno de sus capítulos.

doi: 10.1007/3-540-27477-4_11

Interactive Proofs

Pp. 145-159

doi: 10.1007/3-540-27477-4_12

The PCP Theorem and the Complexity of Approximation Problems

Palabras clave: Polynomial Time; Approximation Ratio; Conjunctive Normal Form; Function Table; Consistency Test.

Pp. 161-184

doi: 10.1007/3-540-27477-4_13

Further Topics From Classical Complexity Theory

Palabras clave: Turing Machine; Computation Path; Satisfying Assignment; Space Bound; Counting Problem.

Pp. 185-199

doi: 10.1007/3-540-27477-4_14

The Complexity of Non-uniform Problems

Pp. 201-217

doi: 10.1007/3-540-27477-4_15

Communication Complexity

Palabras clave: Communication Protocol; Turing Machine; Communication Complexity; Computation Path; Hadamard Matrix.

Pp. 219-249

doi: 10.1007/3-540-27477-4_16

The Complexity of Boolean Functions

Palabras clave: Boolean Function; Communication Complexity; Internal Vertex; Output Gate; Formula Size.

Pp. 251-275