Arytmetyka Presburgera

Arytmetyka Presburgera to teoria pierwszego rzędu liczb naturalnych z dodatkiem , nazwana na cześć Mojżesza Presburgera , który wprowadził ją w 1929 roku. Sygnatura arytmetyki Presburgera zawiera tylko operację dodawania i równość , całkowicie pomijając operację mnożenia . Aksjomaty zawierają schemat indukcji .

Arytmetyka Presburgera jest znacznie słabsza niż arytmetyka Peano , która obejmuje zarówno operacje dodawania, jak i mnożenia. W przeciwieństwie do arytmetyki Peano, arytmetyka Presburgera jest teorią rozstrzygalną . Oznacza to, że dla dowolnego zdania w języku arytmetyki Presburgera można algorytmicznie określić, czy zdanie to można udowodnić na podstawie aksjomatów arytmetyki Presburgera. Asymptotyczna złożoność obliczeniowa tego algorytmu w czasie wykonywania jest co najmniej dwukrotnie wykładnicza , jak wykazali Fischer i Rabin (1974) .

Przegląd

Język arytmetyki Presburgera zawiera stałe 0 i 1 oraz funkcję binarną +, interpretowaną jako dodawanie.

W tym języku aksjomaty arytmetyki Presburgera są uniwersalnymi domknięciami :

1. ¬(0 = x + 1)
2. x + 1 = y + 1 → x = y
3. x + 0 = x
4. x + ( y + 1) = ( x + y ) + 1
5. Niech P ( x ) będzie formułą pierwszego rzędu w języku arytmetyki Presburgera ze zmienną swobodną x (i ewentualnie innymi zmiennymi wolnymi). Wówczas następujący wzór jest aksjomatem: ( P (0) ∧ ∀ x ( P ( x ) → P ( x + 1))) → ∀ y P ( y ).

(5) jest schematem aksjomatów indukcji , reprezentującym nieskończenie wiele aksjomatów. Nie można ich zastąpić żadną skończoną liczbą aksjomatów, to znaczy arytmetyka Presburgera nie jest skończenie aksjomatyzowalna w logice pierwszego rzędu.

Arytmetykę Presburgera można postrzegać jako teorię pierwszego rzędu z równością zawierającą dokładnie wszystkie konsekwencje powyższych aksjomatów. Alternatywnie można go zdefiniować jako zbiór tych zdań, które są prawdziwe w zamierzonej interpretacji : struktura nieujemnych liczb całkowitych ze stałymi 0, 1 oraz dodanie nieujemnych liczb całkowitych.

Arytmetyka Presburgera została zaprojektowana tak, aby była kompletna i rozstrzygalna. Dlatego nie może sformalizować pojęć takich jak podzielność czy pierwotność , ani ogólniej żadnej koncepcji liczbowej prowadzącej do mnożenia zmiennych. Może jednak formułować indywidualne przypadki podzielności; na przykład dowodzi, że „dla wszystkich x istnieje y : ( y + y = x ) ∨ ( y + y + 1 = x )”. Oznacza to, że każda liczba jest parzysta lub nieparzysta.

Nieruchomości

Mojżesz Presburger udowodnił, że arytmetyka Presburgera to:

• spójny : nie ma zdania w arytmetyce Presburgera, które można by wydedukować z aksjomatów, tak że można by również wydedukować jego zaprzeczenie.
• zupełne : dla każdego zdania w języku arytmetyki Presburgera można je albo wydedukować z aksjomatów, albo można wydedukować jego zaprzeczenie.
• rozstrzygalne : Istnieje algorytm , który decyduje, czy dane zdanie w arytmetyce Presburgera jest twierdzeniem, czy nietwierdzeniem.

Rozstrzygalność arytmetyki Presburgera można wykazać za pomocą eliminacji kwantyfikatorów , uzupełnionej rozumowaniem o kongruencji arytmetycznej. Kroki użyte do uzasadnienia algorytmu eliminacji kwantyfikatora można wykorzystać do zdefiniowania rekurencyjnych aksjomatów, które niekoniecznie zawierają schemat aksjomatów indukcji.

Natomiast arytmetyka Peano , która jest arytmetyką Presburgera rozszerzoną o mnożenie, nie jest rozstrzygalna w wyniku negatywnej odpowiedzi na problem Entscheidungs . Zgodnie z twierdzeniem Gödla o niezupełności arytmetyka Peano jest niezupełna, a jej spójności nie da się wewnętrznie udowodnić (ale zobacz dowód spójności Gentzena ).

Złożoność obliczeniowa

Problem decyzyjny dla arytmetyki Presburgera jest interesującym przykładem w teorii złożoności obliczeniowej i obliczeniach . Niech n będzie długością instrukcji w arytmetyce Presburgera. Następnie Fischer i Rabin (1974) udowodnili, że w $.$ przypadku dowód stwierdzenia w logice pierwszego rzędu ma długość co stałej c >0. Stąd ich algorytm decyzyjny dla arytmetyki Presburgera ma czas działania co najmniej wykładniczy. Fischer i Rabin udowodnili również, że dla dowolnej rozsądnej aksjomatyzacji (dokładnie zdefiniowanej w ich pracy) istnieją twierdzenia o długości n , które mają podwójnie wykładniczą dowody długości. Intuicyjnie sugeruje to, że istnieją ograniczenia obliczeniowe tego, co można udowodnić za pomocą programów komputerowych. Praca Fischera i Rabina sugeruje również, że arytmetyka Presburgera może być używana do definiowania formuł, które poprawnie obliczają dowolny algorytm, o ile dane wejściowe są mniejsze niż stosunkowo duże granice. Granice można zwiększyć, ale tylko za pomocą nowych formuł. Oppen (1978) udowodnił potrójnie wykładniczą górną granicę procedury decyzyjnej dla arytmetyki Presburgera .

Berman (1980) wykazał ściślejsze powiązanie złożoności przy użyciu naprzemiennych klas złożoności . Zestaw prawdziwych stwierdzeń w arytmetyce Presburgera (PA) jest pokazany jako kompletny dla TimeAlternations (2 ^{2 n O(1)} , n). Zatem jego złożoność mieści się między podwójnie wykładniczym niedeterministycznym czasem (2-NEXP) a podwójną przestrzenią wykładniczą (2-EXPSPACE). Kompletność podlega redukcji wiele do jednego w czasie wielomianowym. (Należy również zauważyć, że chociaż arytmetyka Presburgera jest powszechnie określana skrótem PA, w matematyce ogólnie PA zwykle oznacza arytmetykę Peano ).

Aby uzyskać bardziej szczegółowy wynik, niech PA(i) będzie zbiorem prawdziwych twierdzeń Σ _i PA, a PA(i, j) zbiorem prawdziwych twierdzeń Σ _i PA z każdym blokiem kwantyfikatora ograniczonym do j zmiennych. „<” jest uważane za wolne od kwantyfikatorów; tutaj kwantyfikatory ograniczone są liczone jako kwantyfikatory. PA(1, j) jest w P, podczas gdy PA(1) jest NP-zupełny. Dla i > 0 i j > 2, PA(i + 1, j) jest Σ _i ^P -zupełne . Wynik twardości potrzebuje tylko j>2 (w przeciwieństwie do j=1) w ostatnim bloku kwantyfikatora. Dla i>0 PA(i+1) wynosi Σ _i ^EXP -complete (i jest TimeAlternations(2 ^{n O(i)} , i)-complete).

Krótki ${\ Displaystyle \ Sigma _ {n}}$ Presburger Arithmetic ( ${\ Displaystyle n> 2}$ ) jest kompletny ${\ Displaystyle \ Sigma _ {n-2} ^ {P}}$ (a zatem NP kompletne dla ${\ displaystyle n = 3}$ ). Tutaj „krótki” wymaga ograniczonego (tj. ${\ Displaystyle O (1)}$ ) rozmiar zdania, z wyjątkiem tego, że stałe całkowite są nieograniczone (ale ich liczba bitów w postaci binarnej liczy się do rozmiaru wejściowego). Również $krótkim$ ”) jest NP-zupełne. Krótki (a zatem ) PA jest w P , a to rozciąga się na parametryczne programowanie liniowe na $liczbach$$wymiarach$

Aplikacje

Ponieważ arytmetyka Presburgera jest rozstrzygalna, istnieją automatyczne dowody twierdzeń dla arytmetyki Presburgera. Na przykład Coq obejmuje taktykę omega dla arytmetyki Presburgera, a asystent dowodu Isabelle zawiera zweryfikowaną procedurę eliminacji kwantyfikatora autorstwa Nipkowa (2010) . Podwójna wykładnicza złożoność teorii sprawia, że ​​niewykonalne jest użycie dowodów twierdzeń na skomplikowanych formułach, ale takie zachowanie występuje tylko w obecności zagnieżdżonych kwantyfikatorów: Nelson i Oppen (1978) opisz automatyczny dowód twierdzeń, który wykorzystuje algorytm simplex na rozszerzonej arytmetyce Presburgera bez zagnieżdżonych kwantyfikatorów, aby udowodnić niektóre przypadki formuł arytmetycznych Presburgera bez kwantyfikatorów. Nowsze rozwiązania teorii modulo spełnialności wykorzystują kompletne techniki programowania liczb całkowitych do obsługi fragmentu teorii arytmetyki Presburgera bez kwantyfikatorów.

Arytmetykę Presburgera można rozszerzyć tak, aby obejmowała mnożenie przez stałe, ponieważ mnożenie jest wielokrotnym dodawaniem. Większość obliczeń indeksu dolnego tablicy mieści się wówczas w obszarze problemów rozstrzygalnych. Podejście to jest podstawą co najmniej pięciu systemów sprawdzania poprawności programów komputerowych , poczynając od Stanford Pascal Verifier w późnych latach 70., a kończąc na systemie Spec# firmy Microsoft z 2005 r.

Relacja liczb całkowitych definiowalna przez Presburgera

Podano teraz niektóre właściwości dotyczące relacji całkowitych definiowalnych w arytmetyce Presburgera. Dla uproszczenia wszystkie relacje omówione w tej sekcji dotyczą nieujemnych liczb całkowitych.

Relacja jest definiowalna przez Presburgera wtedy i tylko wtedy, gdy jest zbiorem półliniowym .

Jednoargumentowa relacja liczb $.$ , to znaczy zbiór nieujemnych liczb całkowitych, jest definiowalna przez Presburgera wtedy i tylko wtedy, gdy jest ostatecznie okresowa To znaczy, jeśli istnieje próg $, że$ dodatni okres taki $}$ , dla wszystkich liczb $takich,$ że ${\ Displaystyle | n | \ geq t}$ , ${\ Displaystyle n \ w R}$ wtedy i tylko wtedy, gdy ${\ Displaystyle n + p \ w R}$ .

Zgodnie z twierdzeniem Cobhama – Semenova relacja jest definiowalna przez Presburgera wtedy i tylko wtedy, gdy jest definiowalna w $k \ geq 2}$ Büchiego o podstawie dla wszystkich $displaystyle$ . Relacja definiowalna w arytmetyce Büchiego podstawy $displaystyle$ k $k'}$ \ dla ${\ displaystyle k}$ i ${\ displaystyle k'}$ multiplikatywnie niezależne liczby całkowite są definiowalne przez Presburgera.

Relacja liczb całkowitych $($$} displaystyle R}$ wszystkie zbiory liczb całkowitych, które są definiowalne w logice pierwszego rzędu z dodawaniem i to znaczy Presburger Arithmetic plus predykat dla $\ displaystyle R$ ) są definiowane przez Presburgera. Równoważnie, $jest$ każdej relacji , która nie $definiowalna$ przez Presburgera, istnieje formuła pierwszego rzędu z dodawaniem i definiuje zbiór liczb całkowitych, których nie można zdefiniować za pomocą samego dodawania.

Charakterystyka Muchnika

Relacje definiowalne przez Presburgera dopuszczają inną charakterystykę: twierdzenie Muchnika. Stwierdzenie jest bardziej skomplikowane, ale doprowadziło do dowodu dwóch poprzednich charakterystyk. Zanim będzie można sformułować twierdzenie Muchnika, należy wprowadzić kilka dodatkowych definicji.

Niech ${\ Displaystyle R \ subseteq \ mathbb {N} ^ {d}}$ będzie zbiorem, sekcja dla $R \$$\ mathbb {N} ^ {d}$ } ${\ Displaystyle i <d}$ i ${\ Displaystyle j \ w \ mathbb {N}}$ jest zdefiniowany jako

${\ Displaystyle \ lewo \ {(x_ {0}, \ ldots, x_ {i-1}, x_ {i + 1}, \ ldots, x_ {d-1}) \ w \ mathbb {N} ^ {d -1}\mid (x_{0},\ldots,x_{i-1},j,x_{i+1},\ldots,x_{d-1})\w R\right\}.}$

$}$ dwa zbiory $-1}) \ w \ mathbb {N} ^ {d}} , zbiór$$d$ liczb - całkowitych $ldots , p_ {$ nazywa się ${\ Displaystyle (p_ {0}, \ kropki, p_ {d-1})}$ -okresowe w ${\ Displaystyle S}$ , jeśli dla wszystkich ${\ Displaystyle (x_{0},\kropki ,x_{d-1})\w S}$ takie, że ${\ Displaystyle (x_ {0}+ p_ {0}, \ kropki, x_ {d-1} + p_ {d-1}) \ w S,}$ wtedy ${ \ Displaystyle (x_ {0}, \ ldots, x_ {d-1}) \ w R}$ wtedy i tylko wtedy, gdy ${\ Displaystyle (x_ {0}+p_{0},\kropki,x_{d-1}+p_{d-1})\w R}$ . dla ${\ Displaystyle s \ in \ mathbb {N}}$ , mówi się, że zbiór jest $S$ w $Displaystyle$ { $}$ , jeśli jest ${\ Displaystyle (p_ {0}, \ ldots, p_ {d-1})} -$ okresowe dla niektórych ${\ Displaystyle (p_ {0}, \ kropki, p_ {d-1}) \ w \ mathbb {Z} ^ {d}}$ takie, że

${\ Displaystyle \ suma _ {i = 0} ^ {d-1} | p_ {i} | <s.}$

Wreszcie, dla ${\ Displaystyle k, x_ {0}, \ kropki, x_ {d-1} \ in \ mathbb {N}}$ niech

${\ Displaystyle C (k, (x_ {0},\ldots ,x_{d-1}))=\left\{(x_{0}+c_{0},\dots ,x_{d-1}+c_{d-1})\mid 0\leq c_{i}<k\right\}}$

oznaczyć sześcian o rozmiarze $,$${\ Displaystyle (x_ {0}, \ kropki, x_ {d-1})}$ mniejszy róg to .

Twierdzenie Muchnika - jest definiowalne przez Presburgera wtedy i tylko wtedy, gdy: ${\ Displaystyle R \ subseteq \ mathbb {N} ^ {d}}$

• jeśli ${\ Displaystyle d> 1}$ , to wszystkie sekcje ${\ Displaystyle R}$ są definiowalne przez Presburgera i R {\ Displaystyle R}
• istnieje ${\ Displaystyle s \ in \ mathbb {N}}$ tak, że dla każdego istnieje ${\ Displaystyle k \ in \ mathbb {N}}$${\ Displaystyle t \ in \ mathbb {N}}$ takie, że dla wszystkich ${\ Displaystyle (x_ {0}, \ kropki, x_ {d-1}) \ w \ mathbb {N} ^ { d}}$ z
  $${\ Displaystyle \ suma _ {i = 0} ^ {d-1} x_ {i}> t,}$$
  ${\ Displaystyle R}$$jest$ re okresowy do $\ Displaystyle C (k, (x_ {0}, \ kropki, x_ {$ .

Intuicyjnie liczba całkowita $długość$ przesunięcia, liczba całkowita $próg$$.$ kostek, a przed okresowością Ten wynik pozostaje prawdziwy, gdy warunek

${\ Displaystyle \ suma _ {i = 0} ^ {d-1} x_ {i}> t}$

jest zastępowane przez ${\ Displaystyle \ min (x_ {0}, \ ldots, x_ {d-1})> t}$ lub przez ${\ Displaystyle \ max (x_ {0}, \ ldots, x_ {d-1})> t}$ .

$,$$,$ zachodzi : istnieje formuła pierwszego rzędu z dodawaniem i predykatem -ary który jeśli i tylko wtedy, gdy $interpretowany$ przez relację definiowalną przez Presburgera. Twierdzenie Muchnika pozwala również udowodnić, że jest rozstrzygalne, czy ciąg automatyczny przyjmuje zbiór definiowalny przez Presburgera.

Zobacz też

• Arytmetyka Robinsona
• Arytmetyka Skolema

Bibliografia

• Berman, L. (1980). „Złożoność teorii logicznych” . Informatyka teoretyczna . 11 (1): 71–77. doi : 10.1016/0304-3975(80)90037-7 .

•   Cobham, Alan (1969). „O zależności bazowej zbiorów liczb rozpoznawalnych przez automaty skończone”. Matematyka Teoria systemów . 3 (2): 186–192. doi : 10.1007/BF01746527 . S2CID 19792434 .

• Cooper, DC (1972). „Dowód twierdzenia w arytmetyce bez mnożenia”. W B. Meltzer i D. Michie (red.). Inteligencja maszynowa . Tom. 7. Wydawnictwo Uniwersytetu w Edynburgu. s. 91–99.

• Eisenbrand, Friedrich; Szmonin, Giennadij (2008). „Parametryczne programowanie liczb całkowitych w ustalonym wymiarze”. Matematyka badań operacyjnych . 33 (4). ar Xiv : 0801.4336 . doi : 10.1287/moor.1080.0320 .

• Enderton, Herbert (2001). Matematyczne wprowadzenie do logiki   (wyd. 2). Boston, MA: Prasa akademicka . ISBN 978-0-12-238452-3 .

•    Ferrante, Jeanne ; Rackoff, Charles W. (1979). Złożoność obliczeniowa teorii logicznych . Notatki z wykładów z matematyki. Tom. 718. Springer-Verlag . doi : 10.1007/BFb0062837 . ISBN 978-3-540-09501-9 . MR 0537764 .

• Fischer, Michael J .; Rabin, Michael O. (1974). „Super-wykładnicza złożoność arytmetyki Presburgera” . Materiały z sympozjum SIAM-AMS z matematyki stosowanej . 7 : 27–41. Zarchiwizowane od oryginału w dniu 15.09.2006 . Źródło 11.06.2006 .

• Ginsburg, Seymour ; Spanier, Edwin Henry (1966). „Półgrupy, formuły Presburgera i języki” . Pacific Journal of Mathematics . 16 (2): 285–296. doi : 10.2140/pjm.1966.16.285 .

• Haase, Christoph (2014). „Podklasy arytmetyki Presburgera i słaba hierarchia EXP”. Postępowanie CSL-LICS . ACM. s. 47:1–47:10. ar Xiv : 1401.5266 . doi : 10.1145/2603088.2603092 .

•   Haase, Christoph (2018). „Przewodnik przetrwania po arytmetyce presburgera” (PDF) . Aktualności ACM SIGLOG . 5 (3): 67–82. doi : 10.1145/3242953.3242964 . S2CID 51847374 .

•    król, Tim; Barrett, Clark W.; Tinelli, Cesare (2014). „Wykorzystanie programowania liczb całkowitych liniowych i mieszanych dla SMT”. 2014 Metody formalne w projektowaniu wspomaganym komputerowo (fmcad 2014) . Tom. 2014. s. 139–146. doi : 10.1109/FMCAD.2014.6987606 . ISBN 978-0-9835-6784-4 . S2CID 5542629 .

• Michaux, chrześcijanin; Villemaire, Roger (1996). „Arytmetyka Presburgera i rozpoznawalność zbiorów liczb naturalnych przez automaty: nowe dowody twierdzeń Cobhama i Semenowa” . Ann. czysta aplikacja Logika . 77 (3): 251–277. doi : 10.1016/0168-0072(95)00022-4 .

•   Mnich, J. Donald Monk (2012). Mathematical Logic (podyplomowe teksty z matematyki (37)) (przedruk w miękkiej oprawie oryginalnego pierwszego wydania z 1976 r.). Skoczek. ISBN 9781468494549 .

• Muchnik, Andriej A. (2003). „Definiowalne kryterium definiowalności w arytmetyce Presburgera i jej zastosowaniach” . Teoria. Oblicz. nauka . 290 (3): 1433–1444. doi : 10.1016/S0304-3975(02)00047-6 .

•   Nelson, Greg; Oppen, Derek C. (kwiecień 1978). „Uproszczenie oparte na wydajnych algorytmach decyzyjnych”. proc. 5. Sympozjum ACM SIGACT-SIGPLAN na temat zasad języków programowania : 141–150. doi : 10.1145/512760.512775 . S2CID 6342372 .

• Nguyen, Danny; Pak, Igor (2017). „Krótka arytmetyka Presburgera jest trudna” (PDF) . 2017 IEEE 58. doroczne sympozjum na temat podstaw informatyki (FOCS) . ar Xiv : 1708.08179 . doi : 10.1109/FOCS.2017.13 . Źródło 2022-09-04 .

• Nguyen Luu, Dahn (2018). Złożoność obliczeniowa arytmetyki Presburgera (teza). Los Angeles: elektroniczne tezy i rozprawy UCLA . Źródło 2022-09-08 .

•   Nipkow, T (2010). „Eliminacja kwantyfikatora liniowego” (PDF) . Dziennik automatycznego rozumowania . 45 (2): 189–212. doi : 10.1007/s10817-010-9183-0 . S2CID 14279141 .

• Oppen, Derek C. (1978). „A 2 ^{2 2 pn} Górna granica złożoności arytmetyki Presburgera” . J. Komputer. Syst. nauka . 16 (3): 323–332. doi : 10.1016/0022-0000(78)90021-1 .

• Presburger, Mojżesz (1929). "Über die Vollständigkeit eines gewissen Systems der Arithmetik ganzer Zahlen, in welchem ​​die Addition als einzige Operation hervortritt". Comptes Rendus du I congrès de Mathématiciens des Pays Slaves, Warszawa : 92–101. , Widzieć Stansifer (1984) za tłumaczenie na język angielski

•    Pugh, William (1991). „Test Omega: szybki i praktyczny algorytm programowania liczb całkowitych do analizy zależności”. Supercomputing '91: Proceedings of the 1991 ACM/IEEE Conference on Supercomputing . Nowy Jork, NY, USA: Association for Computing Machinery: 4–13. doi : 10.1145/125826.125848 . ISBN 0897914597 . S2CID 3174094 .

• Reddy, CR; Loveland, DW (1978). „Arytmetyka Presburgera z ograniczoną zmianą kwantyfikatora”.   Sympozjum ACM na temat teorii informatyki : 320–325. doi : 10.1145/800133.804361 . S2CID 13966721 .

• Siemionow, AL (1977). „Presburgerness predykatów regularnych w dwóch systemach liczbowych”. Sybirsk. Mata. Ż. (po rosyjsku). 18 : 403–418.

• Stansifer, Ryan (wrzesień 1984). Artykuł Presburgera na temat arytmetyki liczb całkowitych: uwagi i tłumaczenie (PDF) (raport techniczny). Tom. TR84-639. Ithaca/NY: Wydział Informatyki, Cornell University.

• Młody, P. (1985). „Twierdzenia Gödla, wykładnicza trudność i nierozstrzygalność teorii arytmetycznych: ekspozycja”. W A. Nerode i R. Shore (red.). Teoria rekurencji, Amerykańskie Towarzystwo Matematyczne . s. 503–522.

• Zoethout, Jetze (1 lutego 2015). Interpretacje w arytmetyce Presburgera (praca licencjacka) (PDF) (praca) . Źródło 2021-10-25 .

Linki zewnętrzne

• Kompletny dowód twierdzeń dla arytmetyki Presburgera autorstwa Philippa Rümmera