How selecting diverse subsets can encode logical circuits
Michael Emmerich, May 12th 2026.
Figure 1 shows how the satisfiability of the 3-SAT clause ('1' OR '2' OR '3') can be encoded as a maximum-diversity subset selection problem. Each disc centre represents a candidate choice, and the task is to select as many non-overlapping discs as possible. The clause is satisfied exactly when such a maximum selection includes one of the blue discs.
(Featuring: Emmerich, M. T. M., Pereverdieva, K., & Deutz, A. H. (2026a). On the complexity of minimum Riesz s-energy subset selection in Euclidean and ultrametric spaces. arXiv. https://arxiv.org/abs/2605.04715)
Maximum diversity is a natural and widely occurring problem. We are given many candidate objects — points, designs, species, solutions, or alternatives — and we want to select a subset that is as varied as possible.
In a metric space, two objects have a distance d(x,y). The basic maximum-diversity question is then simple to state:
Choose k objects so that the chosen set is as diverse as possible.
This question appears in biodiversity, building design exploration, evolutionary multiobjective optimization, and many other settings where we do not want only one “best” solution, but a rich collection of different possibilities. For a comparative view of diversity indicators in multiobjective diversity optimization, see [1]. A related maximum-diversity perspective based on the Solow–Polasky measure is studied in [2].
At first sight, this looks like a geometric selection problem. A perhaps surprising aspect, when one sees these constructions for the first time, is that such a selection problem can encode the solution of a logical circuit. Thus solving a logic circuit and selecting a diverse subset can become equivalent for carefully designed instances.
The central observation is this:
A problem about selecting diverse points can be constructed so that solving it is equivalent to solving a logical formula.
The bridge is made from distances. Distances can encode compatibility and incompatibility. Once this is possible, selecting a diverse subset is no longer only a geometric task; it can represent the feasibility of a logical circuit.
Figure 1 shows a local clause gadget with three cyclic wire gadgets. The discs indicate candidate centres; overlapping discs encode local incompatibilities.
1. MPD: the bottleneck version of diversity
A very simple diversity measure is the minimum pairwise distance criterion, often also called max-min diversity. For a selected set S, define
MPD(S) = min d(x,y).
This measure looks only at the closest pair. A set is good if even its two most similar members are still far apart. There is a simple disc placement analogy we can use to illustrate the problem: Put a disc of the same radius around every selected point. If no two discs overlap, then all selected points are separated by at least twice the radius. Maximizing MPD is like asking:
Given a predefined set of potential disc centers, how can we place as many discs as possible without any two of them overlapping?
However, the MPD is only looking at the bottleneck separation, but not the overall distribution of all pairwise distances. If the closest selected pair stays at distance 1, then MPD does not distinguish whether all other pairs are at distance 1.1, 5, or 100. As long as the closest pair does not improve, the MPD value is unchanged.
2. Riesz energy: diversity as repulsion
Riesz s-energy gives a more sensitive version of the same geometric idea that also sees if distances between pairs of discs that are not bottleneck increase. For a selected subset of points S, define
Es(S) = sum d(x,y)−s.
Here s is a (typically fixed) exponent, e.g. the exponent 2 can be chosen. Now every pair contributes.
- Close pairs contribute a lot.
- Far pairs contribute little.
- The exponent s controls how severely closeness is punished.
To select a diverse set, we minimize this energy. A useful interpretation is a set of mutually repelling points. If two selected points are too close, they create a large energy penalty. If many local distances improve, the total energy notices, even if the absolute closest pair remains unchanged.
This is why Riesz energy is a natural generalization of the MPD viewpoint. MPD asks only:
How bad is the worst pair?
Minimum Riesz energy subset selection asks:
How to find the k subset from the n given points such that the repulsive energy of the point set is minimized (and thereby the diversity is maximized)?
This view has also become useful in evolutionary multiobjective optimization, where one often wants a finite approximation of a Pareto front that is both representative and well spread. [3] studied Riesz s-energy-based reference sets for multiobjective optimization. [4] later studied Riesz s-energy as a diversity indicator in evolutionary multiobjective optimization. More recently, [5] proposed fast high-diversity subset-selection algorithms based on Riesz s-energy.
The exponent s controls the scale at which the closer pairs are emphasized. For moderate s, the energy sees a broad pattern of pairwise interactions. For large s, the closest pairs dominate more and more. In the large-s limit, Riesz energy behaves increasingly like the bottleneck MPD objective. One can therefore view MPD as the limiting case when only the closest pair in the subset matters.
3. When distances become constraints
The key step is to realize that distance can encode compatibility.
Imagine that each candidate point represents a possible choice. Two choices are compatible if they can both be selected. Two choices are incompatible if they should not appear together.
We can encode this geometrically:
large distance ≈ compatible choices.
short distance ≈ incompatible choices.
Then a diverse subset avoids incompatible choices automatically, because incompatible choices are too close together.
In the MPD picture, this is exact: one forbidden close pair immediately reduces the minimum distance. In the Riesz picture, the same close pair creates a large term d(x,y)−s in the energy.
This is the first bridge from diversity to logic:
An inconsistent logical choice can be represented as a forbidden short distance.
[6] used geometric-gadget reasoning to show that packing and covering problems in the plane can encode logical hardness. In the diversity language used here, their construction can be read as a 3-SAT-to-MPD-style reduction: a satisfying truth assignment corresponds to a selection with no forbidden close pair. The Riesz s-energy construction in [7] generalizes this bottleneck picture by replacing the hard MPD threshold with an energy penalty.
4. The logical problem: what is 3-SAT?
Before looking at the geometric gadgets, let us recall the logical problem being encoded. It is the 3-SAT problem, which is famously known to be NP-complete. The foundational work on NP-hardness is generally attributed to the Cook–Levin theorem (1971), which established that the Boolean satisfiability problem (SAT) is NP-complete. We will show that if we could solve Riesz s-energy subset selection (or MPD) for arbitrary values of s and problems in the Euclidean plane, then we could also solve 3-SAT efficiently and solve the “NP-completeness” challenge positively (which we believe is unlikely to happen). The idea is to show that every instance of 3-SAT can be encoded efficiently as an instance of the Riesz s-energy subset-selection problem.
A Boolean variable can be either TRUE or FALSE. For example, x1, x2, and x3 might be three Boolean variables. A literal is either a variable or its negation. Thus xi and ¬xi are both literals. If xi is TRUE, then ¬xi is FALSE, and vice versa.
A clause is an OR of literals. In 3-SAT, each clause has three literals, for example
(xi ∨ ¬xj ∨ xk).
This clause is satisfied if at least one of its three literals is TRUE.
A 3-SAT instance is an AND of such clauses:
C1 ∧ C2 ∧ … ∧ Cm.
The question is:
Can we assign TRUE or FALSE to all variables so that every clause is satisfied?
That is the whole logical problem. Each clause is a little test saying: at least one of these three conditions must hold. A formula is satisfiable if all these little tests can be passed at the same time.
The geometric construction turns this into a disc-selection problem:
Can we select the required number of discs without creating a forbidden close pair?
Or, in Riesz language:
Can we select the required number of points with sufficiently low energy?
Every clause in a 3-SAT instance has the same abstract shape: three literal inputs connected by OR. This is why a single reusable clause gadget is enough. The names of the variables change, and some literals may be negated, but the local logical test is always the same:
ℓ1 ∨ ℓ2 ∨ ℓ3.
So every clause can be represented by the same kind of geometric component. A whole formula is assembled by connecting many copies of this component to the appropriate variable wires.
5. Figure 2: a circuit made of discs
Figure 2: Logical circuit and gadget elements for unit disc placement when encoding 3-SAT instances. A maximum number of discs need to be selected in order to test if all clauses can be satisfied simultaneously.
Figure 2 shows a disk-based gadget layout in the Euclidean plane following the structure of Fowler, Paterson, and Tanimoto. It is the central illustration of this connection in [7]: Figure 2(a) gives the circuit-level view of a 3-SAT instance, Figure 2(b) shows a wire gadget that transmits a Boolean value, Figure 2(c) shows a crossover gadget that lets two wires pass without mixing their truth values, and Figure 2(d) shows a clause gadget that can be completed exactly when at least one incoming literal is true.
A Boolean formula is transformed into a geometric circuit. The circuit is built from local components, or gadgets, and each gadget has a small number of allowed states. The gadgets are arranged so that low-energy or non-overlapping selections correspond exactly to consistent logical choices.
The local rule is simple:
Two nearby choices cannot both be selected.
Each disc centre is a candidate point. Selecting a point means placing the corresponding disc. Some pairs of candidates are arranged so that their discs would overlap, or almost overlap, if both were selected. Such a pair is forbidden.
In the MPD version, the rule is sharp:
Forbidden pair selected ⇒ MPD drops below the threshold.
In the Riesz version, the rule is energetic:
Forbidden pair selected ⇒ Es(S) receives one very large local contribution.
This is the mechanism behind the entire circuit. The logical constraints are represented by distances between candidate disc centres.
In this representation, a false local choice is detected geometrically: the selected discs create an overlap, or the selected centres become too close.
5.1 Figure 2(a): the 3-SAT circuit layout
Figure 2(a), the upper-left panel, should be read as the circuit-level view.
Here the whole 3-SAT formula is drawn as a network. Variables live on one side, clauses live elsewhere, and wires connect variable occurrences to the clauses in which they appear.
For each variable xi, the construction must choose one of two global states:
For each variable, either xi is TRUE or xi is FALSE.
Once this choice is made, the corresponding truth value has to be transmitted to every clause containing xi or ¬xi. This is why the circuit needs wires.
Each clause Cj receives three incoming signals, one for each literal. For example, if
Cj = (x2 ∨ ¬x5 ∨ x7),
then the clause gadget has three input ports:
- a port that opens when x2 is TRUE;
- a port that opens when x5 is FALSE;
- a port that opens when x7 is TRUE.
The clause is satisfied if at least one of these ports is open.
The role of the upper-left panel is therefore to show the big picture:
A Boolean formula becomes a geometric circuit whose signals are TRUE/FALSE choices carried by disc patterns.
5.2 Figure 2(b): the wire gadget
Figure 2(b), the upper-right panel, shows the wire gadget.
A wire carries one Boolean value from one part of the construction to another. In an electronic circuit, a wire might carry high or low voltage. In this geometric circuit, a wire carries one of two possible disc-selection patterns.
The cleanest way to read the wire is as a chain of candidate discs numbered along its length:
1, 2, 3, 4, 5, …
The spacing is chosen so that neighboring candidates cannot both be selected. Candidate 1 conflicts with candidate 2, candidate 2 conflicts with candidate 3, and so on. The construction also fixes the required number of selected discs along the wire. Under this cardinality requirement, there are only two maximal non-overlapping ways to fill the wire:
{1, 3, 5, …}
or
{2, 4, 6, …}.
In words: select all odd-indexed positions, or select all even-indexed positions. These two alternating selections are the two states of the wire.
One of them is declared TRUE, the other FALSE. It does not matter which convention is chosen, as long as the same convention is used consistently throughout the circuit.
This is why the wire transmits information. Choosing the first disc fixes the parity of the whole chain. Once the odd pattern has been chosen, every later choice is forced to remain odd; once the even pattern has been chosen, every later choice is forced to remain even. A mixed pattern would either select two neighboring discs, creating an overlap or short-distance penalty, or fail to select the required number of discs.
The key properties are therefore:
- the wire has exactly two full non-overlapping selection patterns;
- the two patterns are the odd and even positions;
- one pattern represents TRUE and the other represents FALSE;
- changing the truth value means switching the parity of the entire chain;
- an inconsistent local switch creates either a missing selection or a forbidden close pair.
Thus the wire behaves like a physical carrier of a truth value.
In ordinary logic, a wire is a line on a circuit diagram. Here, a wire is an alternating sequence of geometric exclusions. A truth value travels because the parity choice at one end forces the parity choice all along the chain.
5.3 Literal ports: reading a variable or its negation
A wire can expose a small local opening, or literal port, where another gadget can test its state.
For a positive literal xi, the port is open when the wire carries TRUE. For a negative literal ¬xi, the port is open when the same variable wire carries FALSE.
This is how the same variable can appear in several clauses, sometimes positively and sometimes negatively.
The geometry does not need to understand the words “positive” and “negative.” It only needs to route the wire so that the clause gadget sees the correct side of the alternating pattern.
Thus every literal occurrence in the 3-SAT formula becomes one geometric input port.
5.4 Figure 2(c): the crossover gadget
Figure 2(c), the lower-left panel, shows the crossover gadget.
A general 3-SAT circuit is not usually planar. Wires may need to cross. If two geometric wires simply cross each other, their discs may interfere. Then the truth value on one wire could accidentally constrain the truth value on the other. That would corrupt the simulation.
The crossover gadget solves this problem.
It is a small geometric intersection box with four terminals: left, right, top, and bottom. One wire passes horizontally and one vertically. The gadget is designed so that:
- the horizontal input state is transmitted to the horizontal output;
- the vertical input state is transmitted to the vertical output;
- the two transmitted states do not mix;
- all four combinations of horizontal and vertical truth values are allowed;
- inconsistent local choices create an overlap or short-distance penalty.
In logical terms, the crossover does not compute AND, OR, or NOT. It computes identity twice:
(h,v) → (h,v).
This sounds trivial, but geometrically it is crucial. Without crossover gadgets, the circuit would be restricted to planar wiring. With them, a general 3-SAT formula can be laid out as a disc circuit.
The crossover gadget is therefore a routing component. One signal passes through, the other passes across, and neither changes its truth value.
5.5 Figure 2(d): the clause gadget
Figure 2(d), the lower-right panel, shows the clause gadget.
This is the logical test.
Take a clause
C = (ℓ1 ∨ ℓ2 ∨ ℓ3),
where each ℓi is a literal, for example xj or ¬xj.
Three wires arrive at the clause gadget, one for each literal. Each wire presents a port to the clause. The port is open exactly when the corresponding literal is true.
The clause gadget contains one additional required choice: a special clause disc, or a small local set of alternative clause positions, depending on the exact drawing. The important property is:
At least one literal true ⇔ the clause gadget has an admissible local placement.
Equivalently:
All three literals false ⇔ the clause gadget forces a forbidden overlap.
This is the geometric meaning of OR.
If at least one incoming literal is true, then at least one port is open and the clause can be completed without conflict. If all three incoming literals are false, all ports are blocked. The construction still demands the same number of selected discs, so the selection must either omit a required clause choice or create a short-distance conflict.
For MPD, this failure is exact: one forced close pair violates the minimum-distance threshold.
For Riesz energy, this failure is penalized: one forced close pair contributes a large term to the energy. If s is chosen as part of the input, this one local penalty can be made large enough to dominate the harmless background interactions.
A clause is therefore a local feasibility test. If at least one literal is true, the local selection can be completed. If all three literals are false, the required local selection forces a forbidden close pair.
6. Assembling a 3-SAT solver from gadgets
Now the whole construction can be assembled.
Start with a 3-SAT formula.
Variable choices.
For each variable xi, create a source gadget that chooses one of two states: TRUE or FALSE.Wires.
Route the chosen value through wire gadgets to all clauses in which the variable occurs.Negations.
If a clause needs ¬xi, connect the clause to the port that is open when the xi-wire carries FALSE.Crossovers.
Whenever two wires must cross, insert a crossover gadget so that both signals pass through unchanged.Clauses.
Attach one clause gadget for each clause. The gadget can be completed if and only if at least one of its incoming literal ports is open.Cardinality target.
Set the required number k of selected discs so that a complete low-conflict selection must include all required wire, crossover, and clause choices.
The result is a geometric representation of the 3-SAT instance.
If the 3-SAT formula is satisfiable, choose the corresponding TRUE/FALSE state for every variable. The wires transmit these choices, every clause receives at least one true literal, and all gadgets can be completed without a forbidden local conflict.
If the formula is not satisfiable, then for every assignment at least one clause has all three literals false. In the geometric circuit, that clause has no open port. Completing the required selection then forces an overlap or short-distance pair.
Thus:
Formula satisfiable ⇔ geometric circuit has an admissible selection.
For MPD, this equivalence is the clean bottleneck version. This is the 3-SAT-to-MPD reading of the Fowler-style construction of [6].
For Riesz energy, the equivalence becomes an energy comparison, as in [7]. A satisfying assignment gives a low-energy non-overlapping selection. A nonsatisfying assignment forces at least one very short pair. The exponent s controls this comparison: when s is large enough, the contribution of that one short pair dominates the sum of ordinary long-range interactions.
7. Why Riesz energy is subtler than MPD
MPD is a threshold test. One forbidden close pair immediately violates the desired minimum-distance bound.
Riesz energy is a sum over all selected pairs. Every pair contributes, and close pairs contribute much more.
This is why the Riesz proof has an additional issue. A forbidden local pair may be very expensive, but the energy of an admissible configuration contains many harmless pair contributions. One must compare:
one forbidden local penalty
with
the total background energy of many admissible pairs.
The point of choosing s as part of the input is that the short-distance penalty can be made large enough to dominate the background.
Increasing s strengthens the effect of the shortest distances. For sufficiently large s, one forbidden close pair can dominate all admissible longer-distance contributions combined.
The Fowler-style gadget route also gives a useful geometric estimate. A naive estimate would worry that all admissible pair interactions grow quadratically, because k selected points have about k2/2 pairs. But in the planar disc-gadget setting, packing geometry controls the far-field contributions. Around any selected disc, only linearly many non-overlapping discs can appear at each distance layer. Thus the admissible background can be bounded much more sharply than by a rough all-pairs count.
Still, this background grows with the instance size. That is why the Euclidean-plane Riesz proof lets s be part of the input. The exponent is chosen large enough to make a forbidden short pair dominate the remaining admissible energy.
8. A brief theorem note
The main story of this post is the geometry, not the entire complexity landscape. Still, one contextual distinction is useful.
In unrestricted finite metric spaces, where distances need not come from points in the Euclidean plane, Riesz-energy subset selection is already known to be NP-hard even for fixed s; this distinction is discussed in [7]. The Euclidean plane is more restrictive: distances must arise from actual point coordinates. In that setting, [7] prove hardness when s is allowed to be part of the input.
There are also structured cases where Riesz s-energy subset selection can be accomplished efficiently for fixed exponents s. A perhaps surprising open case is the one-dimensional Euclidean line. For MPD, the ordered structure of the line leads to a simple dynamic programming approach. For Riesz s-energy, however, adding one selected point changes its interaction with all previously selected points, and the same state compression is not known to work. Thus the exact complexity of the one-dimensional line case remains open.
By contrast, finite ultrametric spaces form a tractable class. These spaces are naturally represented by rooted trees and occur, for example, in phylogenetic tree diversity, where distances encode evolutionary separation. In [7], we show that minimum Riesz s-energy can be computed exactly over all subsets of size k in finite ultrametric spaces by dynamic programming. The reason is that, in an ultrametric tree, all cross-distances between two sibling subtrees are equal. Hence the interaction between two subproblems depends only on how many selected leaves are taken from each side, not on their individual identities.
This distinction is natural from the story above. In arbitrary metric spaces, one has much more freedom to prescribe distances directly. In the Euclidean plane, distances must be realized by actual geometry, so the proof needs gadgets, packing estimates, and the sensitivity controlled by s. In ultrametric spaces, the hierarchical structure gives enough regularity to make exact optimization possible.
9. Back to diversity
The main point is not only about 3-SAT.
The main point is that a diversity measure can encode computation.
When we ask for a diverse subset, we may think we are merely spreading points apart. But if the candidate distances encode incompatibilities, then selecting a diverse set becomes equivalent to satisfying many logical constraints at once.
In this sense:
- MPD is the bottleneck version;
- Riesz energy is the aggregate pairwise-repulsion version;
- large s connects the two;
- geometric gadgets turn distance constraints into logic constraints.
This is the perhaps surprising link: solving a logic circuit and selecting a diverse subset can become two views of the same constructed problem. A disc can represent part of a truth assignment. A short distance can represent an inconsistency. A low-energy configuration can correspond to a satisfying assignment. The exponent s controls how strongly the Riesz energy approaches the bottleneck behavior of MPD.
References
[1] Pereverdieva, K. G., Deutz, A. H., Ezendam, T., Bäck, T., Hofmeyer, H., & Emmerich, M. T. M. (2025). Comparative analysis of indicators for multi-objective diversity optimization. In H. Singh, T. Ray, J. Knowles, X. Li, J. Branke, B. Wang, & A. Oyama (Eds.), Evolutionary Multi-Criterion Optimization: 13th International Conference, EMO 2025, Canberra, ACT, Australia, March 4–7, 2025, Proceedings, Part II (Lecture Notes in Computer Science, Vol. 15513, pp. 58–71). Springer. https://doi.org/10.1007/978-981-96-3538-2_5
[2] Emmerich, M. T. M., Pereverdieva, K., & Deutz, A. H. (2026b). Selecting a maximum Solow–Polasky diversity subset in general metric spaces is NP-hard. arXiv. https://arxiv.org/abs/2604.05495
[3] Falcón-Cardona, J. G., Ishibuchi, H., & Coello Coello, C. A. (2020). Riesz s-energy-based reference sets for multi-objective optimization. In 2020 IEEE Congress on Evolutionary Computation (CEC) (pp. 1–8). IEEE. https://doi.org/10.1109/CEC48606.2020.9185833
[4] Falcón-Cardona, J. G., Uribe, L., & Rosas, P. (2025). Riesz s-energy as a diversity indicator in evolutionary multiobjective optimization. IEEE Transactions on Evolutionary Computation, 29(4), 1168–1182. https://doi.org/10.1109/TEVC.2024.3405197
[5] Falcón-Cardona, J. G., Juárez, J., Márquez-Vega, L. A., & Emmerich, M. T. M. (2026). Fast high-diversity subset selection for multiobjective optimization by Riesz s-energy. IEEE Transactions on Evolutionary Computation, 30(2), 747–761. https://doi.org/10.1109/TEVC.2025.3570938
[6] Fowler, R. J., Paterson, M. S., & Tanimoto, S. L. (1981). Optimal packing and covering in the plane are NP-complete. Information Processing Letters, 12(3), 133–137. https://doi.org/10.1016/0020-0190(81)90111-3
[7] Emmerich, M. T. M., Pereverdieva, K., & Deutz, A. H. (2026a). On the complexity of minimum Riesz s-energy subset selection in Euclidean and ultrametric spaces. arXiv. https://arxiv.org/abs/2605.04715
Michael Emmerich 