Open AccessGeneric complexity of algorithmic problems over Brandt semigroups
Author(s) -
Alexander Rybalov
Publication year - 2021
Publication title -
journal of physics. conference series
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.21
H-Index - 85
eISSN - 1742-6596
pISSN - 1742-6588
DOI - 10.1088/1742-6596/1791/1/012085
Subject(s) - decidability , semigroup , algorithm , time complexity , computer science , subset sum problem , monoid , discrete mathematics , mathematics , polynomial , mathematical analysis , knapsack problem
In this paper we present a generic polynomial algorithm for the problem about the sum of subset over Brandt semigroup with index set ℕ over any finitely defined group with polynomially decidable word problem. The problem about the sum of subset is a classical combinatorial problem, studied for many decades. This problem is very popular in cryptography, where there are many cryptosystems based on it. Myasnikov, Nikolaev, and Ushakov in 2015 introduced analogs of the problem about the sum of subset for arbitrary groups (semigroups). There are Brandt semigroups for which this problem is NP-complete. Also we propose a polynomial generic algorithm for the problem of identity checking over all finite Brandt monoids B n 1 . This problem is co-NP-complete in the classical sence. Generic algorithms solve problems for almost all inputs with respect to some natural measures on the set of inputs. Supported by Russian Science Foundation, grant 18-71-10028.