Кейбiр сызықты ассоциативтiк емес алгебраның алгоритмдiк күрделiлiгi

Аннотация

Алгебралық күрделілік теориясының негізгі мәселелерінің бірі - алгебралардағы көбейтудің күрделілігі. Ол үшін, біріншіден, алгебра ұғымы анықталып, зерттелетін алгебралар класы бекітіледі. Содан кейін алгоритм түсінігі және оның күрделілігі нақтыланады.

Жалпы мағынада алгебра - амалдардан тұратын жиынтық. Операция, ереже бойынша, жиынның бір немесе бірнеше элементтерінің функциясы ретінде анықталады, оның мәндері жиынтығы бастапқы жиын немесе оның кейбір бөлігі болып табылады. әдетте, қарапайым операциялардың жиынтығы, мысалы, екі битке логикалық операция, екі санды қосу немесе көбейту, содан кейін есептеу моделі бекітілген, оған мысал - кезекті алгоритм, оның әр сатысында бір элементар амал орындалады. Кейбір кірістер мен аралық есептеулердің нәтижелері, олардың нәтижесі алгоритмнің келесі кезеңдерінде элементар әрекетті енгізу үшін қолданыла алады.

Ең маңыздыларына баған бойынша көбейту алгоритмі, және $m \times n$ өлшемді матрицаны $n \times p$ өлшемді матрицаға көбейтетін квадраттық $O(mnp)$ күрделілігі бар (кіріс ұзындығы бойынша) көбейту алгоритмі болып табылады.

               Басқа күрделі кластардан алгебралардың күрделігін бағалау өте маңызды. Бұл жұмыста қарапайым йордан алгебрасы үшін алгебралық жабық өрістен азайтылмайтын симметриялы билинарлы форманың күрделілігінің бағасы, сонымен қатар Кейли-Диксон денесі мен қарапайым өріс үшін Ли алгебрасы үшін баға алынған.