layout: true class: typo, typo-selection --- count: false class: nord-dark, middle, center Lecture 2d: Complexity Theory ============================= @luk036 👨‍💻 · 2026 📅 --- ### Abstract Throughout this presentation, we'll examine how computational problems are classified based on their inherent difficulty, with special attention to NP-completeness and approximation algorithms. We'll investigate why many Electronic Design Automation (EDA) problems are computationally challenging and explore strategies for addressing these complex problems. By the end, you'll understand the theoretical foundations that guide algorithm selection in practical applications. --- ### Overview 📋 .pull-left[ - Complexity theory - NP-completeness. - Approximation classes - Books and online resources. ] .pull-right[  ] --- ### Understanding Complexity Theory Fundamentals - Big O-notation - Classifies algorithms based on their growth rate: O($N$), O($N\log N$), O($N^2$), O($N!$) ... - EDA Problem Scale - $N$ could be very large (multi-million) in EDA problems. - Practical Limits - Most EDA problems have practical limits: signal nets (usually < 200 pins), polygon shapes (usually < 100 vertices), routing layers (usually < 10). - Geometric Properties - Many physical Design problems can exploit locality, symmetry, planarity, or triangle inequality to reduce complexity. --- ### The Challenge of NP-completeness - Many Electronic Design Automation problems fall into the NP-hard category, making them computationally intensive to solve optimally. - Some NP-complete problems allow for good approximations with guaranteed performance ratios (**pseudo-polynomial**), such as bin-packing and knapsack problems. - Other NP-complete problems like Boolean Satisfiability (SAT) are intrinsically not "approximatable" unless P=NP. - For deeper insights, refer to "Complexity and Approximation: Combinatorial Optimization Problems and Their Approximability Properties." --- ### Complexity Classes .mermaid[ <pre> graph TD NPH[NP-Hard] NPC[NP-Complete] NP[NP] P[P] P --> NP NP --> NPC NPC --> NPH style P fill:#4caf50 style NP fill:#2196f3 style NPC fill:#ff9800 style NPH fill:#f44336 </pre> ] --- Approximation Classes --------------------- - NPO-hard - APX-hard - PTAS: polynomial-time approximation scheme - FPTAS: Fully PTAS (pseudo-polynomial) P < FPTAS < PTAS < APX < NPO --- E.g. Minimum Vertex Cover ------------------------- - Instance: Graph $G$ = (${\color{salmon}V}$, ${\color{lime}E}$) - Solution: A vertex cover for $G$, i.e., a subset ${\color{salmon}V'}$ such that, for each edge $(u, v) \in {\color{lime}E}$, at least one of $u$ and $v$ belongs to ${\color{salmon}V'}$ - Measure: Cardinality of the vertex cover, i.e. $|{\color{salmon}V'}|$ - Bad News: APX-complete. - Comment: Admits a PTAS for *planar* graphs [Baker, 1994]. The generalization to $k$-hypergraphs, for $k>1$, is approximable within $k$ [Bar-Yehuda and Even, 1981] and [Hochbaum, 1982a]. (HW: Implement the algorithms.) - Garey and Johnson: GT1 --- Minimum Maximal Matching ------------------------ - Instance: Graph $G$ = (${\color{salmon}V}$, ${\color{lime}E}$). - Solution: A maximal matching ${\color{lime}E'}$, i.e., a subset ${\color{lime}E'}$ such that no two edges in ${\color{lime}E'}$ shares a common endpoint and every edge in ${\color{lime}E} - {\color{lime}E'}$ shares a common endpoint with some edge in ${\color{lime}E'}$. - Measure: Cardinality of the matching, i.e. $|{\color{lime}E'}|$. - Bad News: APX-complete [Yannakakis and Gavril, 1980] - Comment: Transformation from Minimum Vertex Cover (HW: Implement the algorithm) - Garey and Johnson: GT10 --- Minimum Steiner Tree -------------------- - Instance: Complete graph $G$ = (${\color{salmon}V}$, ${\color{lime}E}$), a metric given by edge weights $s: {\color{lime}E} \mapsto N$ and a subset $S \subset {\color{salmon}V}$ of required vertices. - Solution: A Steiner tree, i.e., a sub-tree of $G$ that includes all the vertices in $S$. - Measure: The sum of the weights of the edges in the sub-tree. - Bad News: APX-complete. - Garey and Johnson: ND12 --- Minimum Geometric Steiner Tree ------------------------------ - Instance: Set $P \subset Z \times Z$ of points in the plane. - Solution: A finite set of Steiner points, i.e., $Q \subset Z \times Z$ - Good News: Admits a PTAS [Arora, 1996] - Comment: Admits a PTAS for any *geometric space* of constant dimension $d$, e.g. in the rectilinear metric [Arora, 1997]. - Garey and Johnson: ND13 --- Minimum Traveling Salesperson 🧳🕴 ----------------------------- - Instance: Set $C$ of $m$ cities, distances $d(c_i, c_j) \in N$ for each pair of cities $c_i, c_j \in C$. - Solution: A tour of $C$, i.e., a permutation $\pi : [1..m] \mapsto [1..m]$. - Measure: The length of the tour.  --- Minimum Traveling Salesperson 🧳🕴(II) ----------------------------- - Bad News: NPO-complete - Comment: The corresponding maximization problem (finding the tour of maximum length) is approximable within 7/5 if the distance function is *symmetric* and 63/38 if it is asymmetric [Kosaraju, Park, and Stein, 1994] - Garey and Johnson: ND22 --- Minimum *Metric* TSP -------------------- - Instance: Set $C$ of $m$ cities, distances $d(c_i, c_j) \in N$ satisfying the *triangle inequality* (i.e. $d(a, b) + d(b, c) \geq d(a, c)$) - Solution: A permutation $\pi : [1..m] \mapsto [1..m]$. - Measure: The length of the tour. - Good news: Approximable within 3/2 [Christofides 76] - Bad News: APX-complete. - Comment: A variation in which vertices can be revisited and the goal is to minimize the sum of the latencies of all vertices, where the latency of a vertex $c$ is the length of the tour from the starting point to $c$, is approximable within 29 and is APX-complete --- Minimum Geometric TSP ---------------------- - Instance: Set $C \subset Z \times Z$ of $m$ points in the plane. - Solution: A tour of $C$, i.e., a permutation $\pi : [1..m] \mapsto [1..m]$. - Measure: The length of the tour, where the distance is the discretized Euclidean length. - Good news: Admits a PTAS [Arora, 1996] - Comment: In $\mathbb{R}^m$ the problem is APX-complete for any $l_p$ metric [Trevisan, 1997]. - Garey and Johnson: ND23 --- Application - Punching Machine -----------------------------  --- Summary ------- - Some problems are intrinsically hard -- even good approximation does not exist unless P=NP (NPO-complete). In such cases, heuristic methods are used (see the [next lecture]). - "Better" algorithm could be obtained by exploiting more problem's properties: locality, symmetry, sparsity, planarity, convexity, monotonity, ... etc. --- 📚 Books and Online Resources -------------------------- - G. Ausiello et al. Complexity and Approximation: Combinatorial Optimization Problems and Their Approximability Properties. Springer, 1999. (O224 C737) - M. R. Garey and D. S. Johnson. Computers and Intractability: A Guide to the Theory of NP-completeness. Freeman, 1979. --- count: false class: nord-dark, middle, center .pull-left[ # Q&A 🎤 ] .pull-right[  ]