For relational structures A, B of the same signature, the Promise Constraint Satisfaction Problem PCSP(A,B) asks whether a given input structure maps homomorphically to A or does not even map to B. We are promised that the input satisfies exactly one of these two cases. If there exists a structure C with homomorphisms $Ato Cto B$, then PCSP(A,B) reduces naturally to CSP(C). To the best of our knowledge all known tractable PCSPs reduce to tractable CSPs in this way. However Barto showed that some PCSPs over finite structures A, B require solving CSPs over infinite C. We show that even when such a reduction to finite C is possible, this structure may become arbitrarily large. For every integer $n>1$ and every prime p we give A, B of size n with a single relation of arity $n^p$ such that PCSP(A, B) reduces via a chain of homomorphisms $ Ato Cto B$ to a tractable CSP over some C of size p but not over any smaller structure. In a second family of examples, for every prime $pgeq 7$ we construct A, B of size $p-1$ with a single ternary relation such that PCSP(A, B) reduces via $Ato Cto B$ to a tractable CSP over some C of size p but not over any smaller structure. In contrast we show that if A, B are graphs and PCSP(A,B) reduces to tractable CSP(C) for some finite C, then already A or B has tractable CSP. This extends results and answers a question of Deng et al.
We study a perturbation family of N=2 3d gauge theories and its relation to quantum K-theory. A 3d version of the Intriligator-Vafa formula is given for the quantum K-theory ring of Grassmannians. The 3d BPS half-index of the gauge theory is connected to the theory of bilateral hypergeometric q-series, and to modular q-characters of a class of conformal field theories in a certain massless limit. Turning on 3d Wilson lines at torsion points leads to mock modular behavior. Perturbed correlators in the IR regime are computed by determining the UV-IR map in the presence of deformations.
We study the algebra of Wilson line operators in three-dimensional N=2 supersymmetric U(M) gauge theories with a Higgs phase related to a complex Grassmannian Gr(M,N), and its connection to K-theoretic Gromov-Witten invariants for Gr(M,N). For different Chern-Simons levels, the Wilson loop algebra realizes either the quantum cohomology of Gr(M,N), isomorphic to the Verlinde algebra for U(M), or the quantum K-theoretic ring of Schubert structure sheaves studied by mathematicians, or closely related algebras.
The disk partition function of certain 3d N=2 supersymmetric gauge theories computes a quantum K-theoretic ring for Kahler manifolds X. We study the 3d gauge theory/quantum K-theory correspondence for global and local Calabi-Yau manifolds with several Kahler moduli. We propose a multi-cover formula that relates the 3d BPS world-volume degeneracies computed by quantum K-theory to Gopakumar-Vafa invariants.
The 2d gauged linear sigma model (GLSM) gives a UV model for quantum cohomology on a Kahler manifold X, which is reproduced in the IR limit. We propose and explore a 3d lift of this correspondence, where the UV model is the N=2 supersymmetric 3d gauge theory and the IR limit is given by Giventals permutation equivariant quantum K-theory on X. This gives a one-parameter deformation of the 2d GLSM/quantum cohomology correspondence and recovers it in a small radius limit. We study some novelties of the 3d case regarding integral BPS invariants, chiral rings, deformation spaces and mirror symmetry.
We prove the statement in the title and exhibit examples of quotients of arbitrary nilpotency class. This answers a question by D. F. Holt.
The subalgebra membership problem is the problem of deciding if a given element belongs to an algebra given by a set of generators. This is one of the best established computational problems in algebra. We consider a variant of this problem, which is motivated by recent progress in the Constraint Satisfaction Problem, and is often referred to as the Subpower Membership Problem (SMP). In the SMP we are given a set of tuples in a direct product of algebras from a fixed finite set $mathcal{K}$ of finite algebras, and are asked whether or not a given tuple belongs to the subalgebra of the direct product generated by a given set. Our main result is that the subpower membership problem SMP($mathcal{K}$) is in P if $mathcal{K}$ is a finite set of finite algebras with a cube term, provided $mathcal{K}$ is contained in a residually small variety. We also prove that for any finite set of finite algebras $mathcal{K}$ in a variety with a cube term, each one of the problems SMP($mathcal{K}$), SMP($mathbb{HS} mathcal{K}$), and finding compact representations for subpowers in $mathcal{K}$, is polynomial time reducible to any of the others, and the first two lie in NP.
