Crystal Structure Prediction (csp) is one of the central and most challenging
problems in materials science and computational chemistry. In csp, the goal is
to find a configuration of ions in 3D space that yields the lowest potential
energy. Finding an efficient procedure to solve this complex optimisation
question is a well known open problem. Due to the exponentially large search
space, the problem has been referred in several materials-science papers as
"NP-Hard and very challenging" without a formal proof. This paper fills a gap
in the literature providing the first set of formally proven NP-Hardness
results for a variant of csp with various realistic constraints. In particular,
we focus on the problem of removal: the goal is to find a substructure with
minimal potential energy, by removing a subset of the ions. Our main
contributions are NP-Hardness results for the csp removal problem, new
embeddings of combinatorial graph problems into geometrical settings, and a
more systematic exploration of the energy function to reveal the complexity of
csp. In a wider context, our results contribute to the analysis of
computational problems for weighted graphs embedded into the three-dimensional
Euclidean space.
The $k$-center problem is to choose a subset of size $k$ from a set of $n$
points such that the maximum distance from each point to its nearest center is
minimized. Let $Q=\{Q_1,\ldots,Q_n\}$ be a set of polygons or segments in the
region-based uncertainty model, in which each $Q_i$ is an uncertain point,
where the exact locations of the points in $Q_i$ are unknown. The geometric
objects segments and polygons can be models of a point set. We define the
uncertain version of the $k$-center problem as a generalization in which the
objective is to find $k$ points from $Q$ to cover the remaining regions of $Q$
with minimum or maximum radius of the cluster to cover at least one or all
exact instances of each $Q_i$, respectively. We modify the region-based model
to allow multiple points to be chosen from a region and call the resulting
model the aggregated uncertainty model. All these problems contain the point
version as a special case, so they are all NP-hard with a lower bound 1.822. We
give approximation algorithms for uncertain $k$-center of a set of segments and
polygons. We also have implemented some of our algorithms on a data-set to show
our theoretical performance guarantees can be achieved in practice.
This paper has several purposes. We present through a critical review the
results from already published papers on the constructive semigroup theory, and
contribute to its further development by giving solutions to open problems. We
also draw attention to its possible applications in other (constructive)
mathematics disciplines, in computer science, social sciences, economics, etc.
Another important goal of this paper is to provide a clear, understandable
picture of constructive semigroups with apartness in Bishop's style both to
(classical) algebraists and the ones who apply algebraic knowledge.