English

[VLSI CAD] Why Two-Level Logic Minimization is Challenging

Chase Na - Semiconductor Design Engineer

10 2월 2026 — 7 min read

TL;DR

To solve Two-Level Logic Minimization "exactly," you end up following the Quine–McCluskey (QM) flow.
The bottleneck in QM is the covering (minimum column cover) stage.
- Covering is NP-complete, so the "optimal solution" becomes a proof problem rather than a value.
- SAT is hardly a major issue. The reason is that SAT is fundamentally a decision problem.

EDA uses heuristics + pruning + branch-and-bound to quickly generate "sufficiently good answers".

>What is Two-Level Logic Minimization?

Scenario

Suppose there are three switches.

A: Switch 1
B: Switch 2
C: Switch 3

Light bulb F turns on under the following three conditions.

A=0, B=0, C=1 -> A'B'C
A=0, B=1, C=1 -> A'BC
A=1, B=0, C=1 -> AB'C

That is, F = A'B'C + A'BC + AB'C

👉 3 ANDs + 1 OR
👉 Unnecessarily long.

The process of simplifying this is the optimization process.

Looking closely at the three expressions:

All C = 1
A and B change around

That is, F = C(A'B' + A'B + AB')

Reducing the inner part further,

A'B' + A'B = A'(B' + B) = A'

That is, F = C(A' + AB')

To summarize again.

A' + AB' = A' + B'

Final Result (Two-Level Logic Minimization)

F = (A' + B')C

The number of AND and OR gates has decreased, and the formula has become simpler. At the hardware level, this means fewer cells and interconnects.

In a nutshell

Instead of writing out every single condition for the light bulb to turn on,
leave only the common conditions and group them together.

This is Two-Level Logic Minimization.

To put it more academically:

Express a given Boolean function (f) using the minimal product terms (SOP).

The key ingredients here are:

minterm: Input combinations (or points before cube expansion) where (f=1) in the truth table
prime implicant: The "maximum cube" that cannot be further expanded (merged)
Objective: Cover all minterms (f=1) using prime implicants while minimizing the number of selected primes (or cost).

QM (Quine–McCluskey) Algorithm CostEC%9D%BC-%EC%A0%95%ED%99%95%ED%95%B4%EB%B2%95">QM (Quine–McCluskey) Algorithm (Exact Solution)

Logic Synthesis and Verification, Jie-Hong Roland Jiang 江介宏 Department of Electrical Engineering National Taiwan University

In the figure above, number 4 is the main body.

Solve the minimum column conversion problem for B (unate conversion problem)

First, let's understand QM.

Light Bulb Problem Revisited

There were exactly three cases where the light bulb F turned on.

EC%8B%9C%EC%9E%91">Light Bulb Problem Restart
Light bulb F turned on in exactly three cases.
1. A off, B off, C on
2. A off, B on, C on
3. A on, B off, C on
For now, let's just think of it this way:
It's how a computer automatically combines conditions using only rules.
The rule is simple:
- A: Both off
- C: Both on
- Only B differs
With just this one condition
- (A=0, B=0, C=1)
- (A=0, B=1, C=1)
  Both cases can be explained simultaneously
- B: Both off
- C: Both on
- Only A differs
With this single condition
- (A=0, B=0, C=1)
- (A=1, B=0, C=1)
  Explains both cases simultaneously
- A is also different
- B is also different
Two conditions remain:
- Condition X: "A is irrelevant, B is off, and C is on"
- Condition Y: "A is off, B is irrelevant, and C is on"
Comparing these two:
- A is different
- B is different
- ✔️ Exhaustively list all "on" cases
- ✔️ Automatically merge cases where only one switch differs
- ✔️ Stop when no further merging is possible
- ✔️️ The remaining conditions are minimal logic
Pushing this rule to its absolute limit is what defines Quine–McCluskey.
If the number of variables is n,
- Possible input cases: 2^n
- Maximum number of minterms: 2^n
Example:
- 6 variables → 64 cases
- 10 variables → 1,024 cases
- 15 variables → 32,768 cases
- 20 variables → 1,048,576 cases
The worst part of QM is the end.
- Increasing number of prime implicants
- Exploring "Can this cover all minterms?"
- This is the Set Cover problem
SAT (Boolean Satisfiability) is precisely this question.
If it exists, it's SAT; if not, it's UNSAT.
The key point is that it's a Yes/No (existence) problem.
This is where many people get confused, but the conclusion is simple.
- The SAT solver terminates once it finds one solution.
- For UNSAT, proof that "it is impossible" (in practice, conflict-driven learning) accumulates, strengthening pruning.
- Therefore, even without examining all possibilities, early exit frequently occurs.
This is optimization's true demand.
In other words,
- Finding a solution better than the initial one is just the beginning
- You must demonstrate that no better solution exists to claim "global optimality".
The reason this is difficult is that it ultimately requires extensively ruling out the combinatorial space.
Even with just the three lightbulb examples we saw earlier, multiple calculations were required. However, looking at smartphone semiconductors designed since 2020, they contain over 10 billion transistors.
The typical way to convert Optimization into SAT:
- Apply a bound like "cost ≤ k" and solve the SAT problem
  - If it works, reduce k and run SAT again
  - If it doesn't work, increase k or stop (= binary search/iterative tightening)
In other words, we solve SAT multiple times, not just once. Moreover, as k decreases, constraints often become stricter, making the problem harder.
Practical EDA typically involves:
- Timing / Area / Power / Congestion / Routability … multi-objective
- Constraints also have multiple conditions like corner/mode settings
- Cost functions aren't continuous but change abruptly in a rugged landscape
Therefore, the term "optimal" becomes more dangerous.
In most cases, "best-found / improved over baseline" is a more honest expression.
- SAT (Existence Problem): "Is there at least one satisfying solution?" → Termination possible upon finding one
- Optimization (Optimality Problem): "Is the minimum/maximum correct?" → Must prove "no better solution" exists to terminate
In other words,
When encountering terms like "global optimum" or "optimal solution" in a paper, you must verify the following checklist.
Checklist:
- Is there actual proof of optimality guarantee?
- What is the problem size (n)?
- Is the comparison against a heuristic baseline or against "optimal"?
- What is the objective? (Timing only? Area only? Power only?)
- Is there seed repetition/distribution? (verify robustness)
- Is it reproducible?
Two-Level Logic Minimization is a great educational example.
Because with just one instance of NP-complete covering, you can easily derive the reality of EDA as a whole (placement / routing / scheduling / …).

EDA is engineering.
The goal is "fast, stable, and metric improvement".

Conclusion: The hard part in EDA isn't "computation," it's "optimality proof."

The fundamental attitude required for semiconductor design evaluation: Skepticism

Optimization requires proof of absence (no better solution), not finding a value.

The Difference Between "Enumeration vs Optimization"

(4) EDA is usually not single-objective but more complex

(3) There's a standard trick for solving Optimization using SAT, but it's heavy because it involves "iteration"

"Prove that a better year does not exist.""

(2) Optimization never ends because it requires "proof of optimality"

Why is SAT good at work, but Optimization keeps being hard?

"Does at least one input assignment exist that makes this logical expression TRUE?"

What is SAT?

NP-hard, requiring checking all possibilities for an answer

3️⃣ The Real Hell is "Prime Implicant Selection"

QM means "covering every possible case"
It's already over at this stage

Why? The number of cases is insane

Quine–McCluskey (QM) suffers from "exponential computational explosion".
Even a slight increase in variables overwhelms the computer.

Among the cases where the light bulb turns on,
if changing just one switch still keeps it on,
you don't need to worry about that switch.

This is the essence of Quine–McCluskey

Since the two switches are different,
they cannot be combined any further

2️⃣ Check if further merging is possible

If both switches are different
QM rules prohibit merging

Case 2 vs Case 3

A is irrelevant
“B must be off, and only C must be on"

Case 1 vs Case 3

B is irrelevant
"A must be off, and only C must be on"

Case 1 vs Case 2

1️⃣ First Merge (When Only One Switch Differs)

If two cases where the light bulb turns on differ by only one switch,
that switch is irrelevant.

What is Quine–McCluskey?

"There is an exact list of switch states that causes the light bulb to turn on."

Without knowing the global optimal, "50% relative to optimal" is not valid.
Instead, practical EDA typically evaluates based on the following criteria.

PPA: Did the absolute values for Area/Power/Timing (WNS/TNS, etc.) improve compared to modern methodologies?
Improvement vs. Baseline (As Is vs. To Be): How much better is it compared to previous runs/options/tools?
Robustness: Are the results stable even when changing seeds/corners?
Efficiency vs. Runtime

From here, we typically use:

branch-and-bound
Solve using a heuristic that creates a "good bound".

combinatorial explosion begins

Therefore, while QM provides the "exact minimum," it becomes difficult to use in industrial settings as the scale increases.

SAT solvers terminate once they find one solution.
UNSAT solvers prove "impossibility" (in practice, finding one solution is enough).
finding one solves it."

This is the essence of QM:

"Do this minterm and that minterm differ by exactly one bit?"

That is,

If there are M minterms,
Number of comparisons ≈ M²

Example:

1,000 minterms → 1 million comparisons
10,000 minterms → 100 million comparisons
30,000 minterms → 900 million comparisons