Complexity Classifications of Boolean Constraint Satisfaction Problems - Rilegato

Creignou, Nadia; Khanna, Sanjeev; Sudan, Madhu

 
9780898714791: Complexity Classifications of Boolean Constraint Satisfaction Problems
Rilegato
ISBN 10: 0898714796 ISBN 13: 9780898714791
Casa editrice: Society for Industrial and Applied Mathematics, 2001

Sinossi

Presents a novel form of a compendium that classifies an infinite number of problems by using a rule-based approach.

Le informazioni nella sezione "Riassunto" possono far riferimento a edizioni diverse di questo titolo.

Descrizione del libro

This book presents a novel and compact form of a compendium that classifies an infinite number of problems by using a rule-based approach. This enables practitioners to determine whether or not a given problem is known to be computationally intractable.

Contenuti

Preface; 1. Introduction; 2. Complexity Classes; 3. Boolean Constraint Satisfaction Problems; 4. Characterizations of Constraint Functions; 5. Implementation of Functions and Reductions; 6. Classification Theorems for Decision, Counting and Quantified Problems; 7. Classification Theorems for Optimization Problems; 8. Input-Restricted Constrained Satisfaction Problems; 9. The Complexity of the Meta-Problems; 10. Concluding Remarks; Bibliography; Index.

Le informazioni nella sezione "Su questo libro" possono far riferimento a edizioni diverse di questo titolo.

Editore
Society for Industrial and Applied Mathematics
Data di pubblicazione
2001
Lingua
Inglese
ISBN 10 
0898714796
ISBN 13 
9780898714791
Rilegatura
Copertina rigida
Numero di pagine
118
Contatto del produttore
non disponibile
Persona responsabile
non disponibile