标题： 关于抽象和具体的小人 显示英文标题

标题： On abstract and concrete minions

摘要： 这篇论文具有说明性质。 我们分析抽象小人（可以描述为从有限序数范畴到集合的函子）与具体小人之间的联系，具体小人是关系结构之间的多态性集合$\mathrm{Pol}(A, B)$，这些多态性是$A^k \to B$，关系结构是$A$和$B$。 函子结构出现是因为一个函数$\alpha\colon n \to k$将一个$n$元的多态性$f\colon A^n \to B$转换为多态性$(x_0, \ldots, x_{k-1}) \mapsto f(x_{\alpha (0)}, \ldots, x_{\alpha (n-1)})$。 这些数据与有限域上的约束满足问题相关，因为矿工同态$\mathrm{Pol}(A, B) \to \mathrm{Pol}(A', B')$会导致从承诺约束满足问题$\mathrm{PCSP}(A', B')$到$\mathrm{PCSP}(A, B)$的对数空间归约。 因此，它们对于理解有限域结构上的多态性矿工的同态序是有价值的，尤其是因为尚不清楚约束满足问题的 P vs. NP 复杂性二分法是否能扩展到更一般的承诺设置中。 至关重要的是，尽管在一些论文中隐式地用于解决非平凡问题，但抽象矿工的概念迄今为止尚未被暴露出来，尽管关于函子范畴已有许多了解。 本文的目标是开始弥补这一差距，并将范畴论中的已知构造应用于矿工。 此外，我们确定了一个条件，在该条件下抽象矿工可以作为有限域上的具体矿工出现，并推导出许多构造在这些具体性假设下保持稳定。 我们将得出结论，所讨论的一些同态序是不可数的分配有界格，而且是（双）Heyting 代数。 在此过程中，我们收集了与抽象和具体矿工相关的开放问题。 显示英文摘要

摘要： This thesis is expository in nature. We analyze the connection between abstract minions, which can be described as functors from the category of finite ordinals to sets, and concrete minions, which are sets $\mathrm{Pol}(A, B)$ of polymorphisms $A^k \to B$ between relational structures $A$ and $B$. The functorial structure arises because a function $\alpha\colon n \to k$ transforms an $n$-ary polymorphism $f\colon A^n \to B$ to the polymorphism $(x_0, \ldots, x_{k-1}) \mapsto f(x_{\alpha (0)}, \ldots, x_{\alpha (n-1)})$. This data is relevant to the constraint satisfaction problems over finite domain, because minion homomorphisms $\mathrm{Pol}(A, B) \to \mathrm{Pol}(A', B')$ give rise to log-space reductions from the promise constraint satisfaction problem $\mathrm{PCSP}(A', B')$ to $\mathrm{PCSP}(A, B)$. Thus, they are valuable to understand the homomorphism order of polymorphism minions over finite-domain structures, especially since it is unknown whether the P vs. NP complexity dichotomy of constraint satisfaction problems extends to the more generalized promise setting. Crucially, although implicitly used in some papers to solve nontrivial problems, the concept of an abstract minion has not been exposed on so far, even though much is known about functor categories. The aim of this thesis is to start closing this gap, and to apply well-known constructions from category theory to minions. Furthermore, we identify a condition under which an abstract minion can arise as a concrete one over a finite domain, and deduce that many constructions remain stable under some of these concreteness assumptions. We will conclude that some of the homomorphism orders in question are uncountable distributive bounded lattices, and moreover (bi-) Heyting algebras. Along the way, we collect open questions related to abstract and concrete minions.