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_1

Introduction

Palabras clave: Complexity Theory; Binary Decision Diagram; Algorithmic Problem; Theoretical Computer Science; Travel Salesperson Problem.

Pp. 1-10

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

Algorithmic Problems & Their Complexity

Palabras clave: Short Path; Turing Machine; Computation Step; Input Format; Algorithmic Problem.

Pp. 11-24

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

Fundamental Complexity Classes

Palabras clave: Decision Problem; Turing Machine; Correct Result; Complexity Class; Computation Path.

Pp. 25-41

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

Reductions — Algorithmic Relationships Between Problems

Pp. 43-61

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

The Theory of NP-Completeness

Palabras clave: Polynomial Time; Decision Problem; Turing Machine; Conjunctive Normal Form; Deterministic Algorithm.

Pp. 63-75

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

NP-complete and NP-equivalent Problems

Pp. 77-87

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

The Complexity Analysis of Problems

Pp. 89-97

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

The Complexity of Approximation Problems — Classical Results

Palabras clave: Polynomial Time; Approximation Problem; Maximization Problem; Approximation Ratio; Knapsack Problem.

Pp. 99-114

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

The Complexity of Black Box Problems

Palabras clave: Function Class; Search Heuristic; Deterministic Algorithm; Search Point; Unimodal Function.

Pp. 115-125

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

Additional Complexity Classes and Relationships Between Complexity Classes

Pp. 127-144