Arytmetyka Presburgera – układ aksjomatyczny liczb naturalnych z dodawaniem. Nazywana jest także arytmetyką Peana bez mnożenia. Język arytmetyki Presburgera zawiera 0 i 1, binarną funkcję + określaną jako dodawanie oraz relację równości.
Aksjomaty Główne aksjomaty arytmetyki to:
Niech będzie formułą w języku Presburgera i niech dana będzie określona zmienna . Wtedy następująca formuła jest aksjomatem:
Ostatni aksjomat określany jest schematem indukcji reprezentującym nieskończoną liczbę aksjomatów.
Rozstrzygalność i własności W 1929 roku Mojżesz Presburger udowodnił, że arytmetyka ta jest rozstrzygalna. Rozstrzygalność (decydowalność) problemu matematycznego to następująca jego właściwość: zawsze można określić, czy dana odpowiedź na pytanie stawiane przez problem jest poprawna. Presburger udowodnił także, że taka arytmetyka jest niesprzeczna i zupełna (istnieje dowód T lub negacji T).
Złożoność obliczeniowa Arytmetyka Presburgera przydaje się do rozstrzygania problemów, choć czas działania zgrubnego algorytmu jest niejasny. Czas najlepszych algorytmów jest potrójnie wykładniczy. Niech będzie długością twierdzenia w arytmetyce Presburgera; Fischer i Rabin (1974) udowodnili, że każdy algorytm sprawdzający prawdziwość twierdzenia musi wykonać w pesymistycznym przypadku co najmniej kroków dla pewnej stałej .
Kategoria:Arytmetyka