Я хочу уточнить, что значит дать алгебру в качестве входных данных для алгоритма, и я не нашел много литературы по этому поводу. Итак, сначала я хочу спросить, можете ли вы порекомендовать книгу или статью, которая посвящена теме анализа сложности алгебр над полями и четко определяет решение проблемы .
После некоторого поиска я нашел кое-что и хочу поделиться этим здесь, а также спросить, имеют ли определения смысл и соответствуют ли литературе (если есть):
Определение: Пусть поле и конечно порожденная коммутативная F - алгебра с аддитивным базисом б 1 , ... , б п ∈ F . Теперь мы хотим захватить мультипликативную структуру алгебры и, следовательно, записать каждое произведение базовых элементов в виде линейной комбинации всех базовых элементов: ∀ 1 ≤ i , j , k ≤ n : ∃ a i j k : b i b j = н ∑Я J K называютсякоэффициентами структуры. У нас прямо это есть: A≅ F [ b 1 ,…, b n ]
Теперь можно определить следующую задачу решения: {(A,B)∣A,B коммутативные F- алгебры с базисом b 1 ,… b n и A≅B}.Чтобы задать изоморфизм , достаточно , чтобы написать каждый ф ( б I ) в качестве линейной комбинации элементов базиса B .
Что-то в этом определении кажется вам странным или вы думаете, что с этим можно работать?
Ответы:
источник
Вычислимость по математической структуре является давней и устоявшейся областью исследований. Например, см .:
Эдвард Р. Гриффор, « Справочник по теории вычислимости », 1999
Леонидович Ершов, " Справочник по рекурсивной математике: рекурсивная алгебра, анализ и комбинаторика ", 1998
или Google для:
источник