Computational Intractability
Autor Erik D. Demaine, William Gasarch Gasarchen Limba Engleză Hardback – 20 oct 2026
Preț: 848.26 lei
Preț vechi: 1009.83 lei
-16% Nou
Puncte Express: 1272
Cartea se retipărește
Doresc să fiu notificat când acest titlu va fi disponibil:
Se trimite...
Specificații
ISBN-13: 9780262550772
ISBN-10: 0262550776
Pagini: 600
Dimensiuni: 181 x 235 x 29 mm
Greutate: 1.01 kg
Editura: MIT Press Ltd
ISBN-10: 0262550776
Pagini: 600
Dimensiuni: 181 x 235 x 29 mm
Greutate: 1.01 kg
Editura: MIT Press Ltd
Notă biografică
Erik D. Demaine is Professor of Computer Science at MIT and a MacArthur Fellow. His previous books include Geometric Folding Algorithms and Games, Puzzles, and Computation.
William Gasarch is Professor of Computer Science at the University of Maryland, where his research focuses on complexity theory, combinatorics, and Ramsey Theory. His previous books include Problems with a Point and Mathematical Muffin Morsels.
MohammadTaghi Hajiaghayi is Jack and Rita G. Minker Professor of Computer Science at the University of Maryland. He is a Guggenheim Fellow, ACM Fellow, IEEE Fellow, AAAS Fellow, EATCS Fellow, and Blavatnik Honoree.
William Gasarch is Professor of Computer Science at the University of Maryland, where his research focuses on complexity theory, combinatorics, and Ramsey Theory. His previous books include Problems with a Point and Mathematical Muffin Morsels.
MohammadTaghi Hajiaghayi is Jack and Rita G. Minker Professor of Computer Science at the University of Maryland. He is a Guggenheim Fellow, ACM Fellow, IEEE Fellow, AAAS Fellow, EATCS Fellow, and Blavatnik Honoree.
Cuprins
Preface
0. Computational Complexity Crash Course
I. NP and Its Variants
1. NP-Hardness via SAT
2. NP-Hardness via Planar SAT
3. NP-Hardness via Circuit SAT
4. NP-Hardness via Hamiltonian Cycle
5. NP-Hardness via 3-Partition
6. Exponential Time Hypothesis
7. Parameterized Complexity
8. Basic Lower Bounds on Approximability via PCP and Gap Reductions
9. Inapproximability
10. Unique Games Conjecture
II. Above NP
11. Counting Problems
12. Existential Theory of the Reals
13. PSPACE-Hardness
14. Beyond PSPACE But Decidable
15. Undecidable Problems
16. Contraint Logic
III. Below NP
17. 3SUM Conjecture: A Method for Obtaining Quadratic Lower Bounds
18. APSP Conjecture: A Method for Obtaining Cubic Lower Bounds
19. Lower Bounds for Online Algorithms
20. Lower Bounds on Streaming Algorithms
21. Parallel Algorithms: The MPC and AMPC Models
22. Nash Equilibria and Polynomial Parity Arguments for Directed Graphs
23. Quantum Computing
Bibliography
Index
0. Computational Complexity Crash Course
I. NP and Its Variants
1. NP-Hardness via SAT
2. NP-Hardness via Planar SAT
3. NP-Hardness via Circuit SAT
4. NP-Hardness via Hamiltonian Cycle
5. NP-Hardness via 3-Partition
6. Exponential Time Hypothesis
7. Parameterized Complexity
8. Basic Lower Bounds on Approximability via PCP and Gap Reductions
9. Inapproximability
10. Unique Games Conjecture
II. Above NP
11. Counting Problems
12. Existential Theory of the Reals
13. PSPACE-Hardness
14. Beyond PSPACE But Decidable
15. Undecidable Problems
16. Contraint Logic
III. Below NP
17. 3SUM Conjecture: A Method for Obtaining Quadratic Lower Bounds
18. APSP Conjecture: A Method for Obtaining Cubic Lower Bounds
19. Lower Bounds for Online Algorithms
20. Lower Bounds on Streaming Algorithms
21. Parallel Algorithms: The MPC and AMPC Models
22. Nash Equilibria and Polynomial Parity Arguments for Directed Graphs
23. Quantum Computing
Bibliography
Index