Reviews for Advanced Asic Chip Synthesis Using Synopsys. Design Compiler. Physical Compiler. And Primetime.

The average rating for Advanced Asic Chip Synthesis Using Synopsys. Design Compiler. Physical Compiler. And Primetime. based on 2 reviews is 3.5 stars.

Review # 1 was written on 2015-10-17 00:00:00 Liam Astle The current state of knowledge of approximation algorithms. As every undergraduate CS major learns (and high schoolers can be taught to understand), NP-complete problems most likely have no polynomial algorithms to solve them. In the 30 years since this question was first posed (actually, it was first posed in a letter Gödel wrote to von Neumann in 1954, but neither great man publicized it) no one has been able to prove it, or prove that it is impossible to prove it, and no one has been able to refute it either. Although the definition of NP talks about decision problems, many NP-complete problems are more naturally formulated as optimization problems; for example, "Given a graph G and an integer k, does G have a clique of size k or larger?" is a decision problem, but it is equivalent to the optimization problem, "Given a graph G, what is the maximum size of a clique in G?" or, "Given a graph G, what is a clique of the maximum size in G?". Unless P=NP, an efficient algorithm that solves the optimization problem exactly doesn't exist. What about an efficient algorithm that solves the optimization problem approximately - say, "Given a graph G, what is a clique such that its size is at least 1/2 of the maximum clique size?" Surely, if such an algorithm were to exist, this would have huge practical implications. This book describes (and gives a rough outline of the proof of) the PCP theorem, which is a very beautiful theorem proven in the 1990s, a consequence of which is that unless P=NP, there is no efficient algorithm that would solve the maximum clique problem to any guaranteed constant factor of approximation (the same is true for several more NP-complete problems, though not all). The book also describes several approximation techniques and examples of proving inapproximability and ends with a Garey and Johnson-like catalogue of NP-complete problems and the knowledge of their approximability or inapproximability. Overall, this book is less interesting than Vijay Varirani's Approximation Algorithms, which goes through several representative NP-complete problems and discusses in detail the approximation algorithm for each. Vazirani's book is a monograph, while this book is a textbook. If you are only going to read one book on approximation algorithms, get Vazirani's book and not this one.

Review # 2 was written on 2019-11-01 00:00:00 Howard Kim Gosh I really don't feel like reading this book, but my advisor is teaching the class and he asked me to take it because he didn't have enough students enrolled. ;_;