اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدDeciding absorption
77
0
0.0
(
0
)
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
We characterize absorption in finite idempotent algebras by means of Jonsson absorption and cube term blockers. As an application we show that it is decidable whether a given subset is an absorbing subuniverse of an algebra given by the tables of its basic operations.
قيم البحث
اقرأ أيضاً
In this paper we investigate the computational complexity of deciding if a given finite algebraic structure satisfies a fixed (strong) Maltsev condition $Sigma$. Our goal in this paper is to show that $Sigma$-testing can be accomplished in polynomial
time when the algebras tested are idempotent and the Maltsev condition $Sigma$ can be described using paths. Examples of such path conditions are having a Maltsev term, having a majority operation, and having a chain of Jonsson (or Gumm) terms of fixed length.
We show that for a fixed positive integer k one can efficiently decide if a finite algebra A admits a k-ary weak near unanimity operation by looking at the local behavior of the terms of A. We also observe that the problem of deciding if a given fini
te algebra has a quasi Taylor operation is solvable in polynomial time by looking, essentially, for local quasi Siggers operations.
This paper investigates the computational complexity of deciding if a given finite idempotent algebra has a ternary term operation $m$ that satisfies the minority equations $m(y,x,x) approx m(x,y,x) approx m(x,x,y) approx y$. We show that a common po
lynomial-time approach to testing for this type of condition will not work in this case and that this decision problem lies in the class NP.
We study the hardness of the dihedral hidden subgroup problem. It is known that lattice problems reduce to it, and that it reduces to random subset sum with density $> 1$ and also to quantum sampling subset sum solutions. We examine a decision versio
n of the problem where the question asks whether the hidden subgroup is trivial or order two. The decision problem essentially asks if a given vector is in the span of all coset states. We approach this by first computing an explicit basis for the coset space and the perpendicular space. We then look at the consequences of having efficient unitaries that use this basis. We show that if a unitary maps the basis to the standard basis in any way, then that unitary can be used to solve random subset sum with constant density $>1$. We also show that if a unitary can exactly decide membership in the coset subspace, then the collision problem for subset sum can be solved for density $>1$ but approaching $1$ as the problem size increases. This strengthens the previous hardness result that implementing the optimal POVM in a specific way is as hard as quantum sampling subset sum solutions.
We study the problem of whether a given finite algebra with finitely many basic operations contains a cube term; we give both structural and algorithmic results. We show that if such an algebra has a cube term then it has a cube term of dimension at
most $N$, where the number $N$ depends on the arities of basic operations of the algebra and the size of the basic set. For finite idempotent algebras we give a tight bound on $N$ that, in the special case of algebras with more than $binom{|A|}2$ basic operations, improves an earlier result of K. Kearnes and A. Szendrei. On the algorithmic side, we show that deciding the existence of cube terms is in P for idempotent algebras and in EXPTIME in general. Since an algebra contains a $k$-ary near unanimity operation if and only if it contains a $k$-dimensional cube term and generates a congruence distributive variety, our algorithm also lets us decide whether a given finite algebra has a near unanimity operation.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
