Chcę sprecyzować, co to znaczy podać algebrę jako dane wejściowe do algorytmu i nie znalazłem zbyt wiele literatury na ten temat. Najpierw chciałbym zapytać, czy możesz polecić książkę lub artykuł, który porusza temat analizy złożoności algebr nad polami i jasno określa problem decyzyjny .
Po kilku kopaniach znalazłem coś i chcę się nim podzielić, a ponadto zapytam, czy definicje mają sens i czy są zgodne z literaturą (jeśli istnieje):
Definicja: Niech będzie pola i być skończenie przemienne wygenerowane F -algebra z dodatków oparciu b 1 , ... , b n ∈ F . Chcemy teraz uchwycić multiplikatywną strukturę algebry i dlatego piszemy każdy iloczyn elementów podstawowych jako liniową kombinację wszystkich elementów podstawowych: ∀ 1 ≤ i , j , k ≤ n : ∃ a i j k : b i b j = n ∑I j k nazywane sąwspółczynnikami struktury. Mamy to bezpośrednio: A≅ F [ b 1 ,…, b n ]
Teraz można zdefiniować następujący problem decyzyjny: {(A,B)∣A,B przemienne F- algebry na podstawie b 1 ,… b n i A≅B}.Aby określić izomorfizmem wystarczy napisać każdą cp ( b I ) jako liniowa kombinacja elementów na bazie pensjonatów .
Czy coś w tej definicji wydaje ci się dziwne, czy uważasz, że można z tym pracować?
źródło
Odpowiedzi:
źródło
Obliczalność struktury matematycznej jest długim i dobrze ugruntowanym obszarem badań. Na przykład zobacz:
Edward R. Griffor, „ Handbook of Computability Theory ”, 1999
Leonidovich Ershov, „ Handbook of Recursive Mathematics: Recursive Algebra, Analysis and Combinatorics ”, 1998
lub google dla:
źródło