Czy rachunek afiniczny lambda może rozwiązać każdy problem w P?

W Zaawansowanych tematach w typach i językach programowania w rozdziale o podstrukturalnych systemach typów wspomniano, że „starannie spreparowany” rachunek afiniczny lambda z kombinatorem rekurencyjnym dla list może wpisywać tylko terminy, które mają wielomianowy czas działania (nie przedstawić dowód ze względu na złożoność). Byłoby to bardzo interesujące, gdybyśmy mogli rozwiązać każdy problem w P. Mogłabym spróbować znaleźć rozwiązanie problemu P-zupełnego za pomocą rachunku przedstawionego przez Nie jestem pewien, czy to by cokolwiek udowodniło. Wydaje mi się, że nie oznacza to, że może wykonać wszystkie redukcje konieczne do zastosowania rozwiązania problemu P-zupełnego (choć na pewno wydaje się prawdopodobne).

Jeśli afiniczny rachunek lambda nie jest w stanie rozwiązać dokładnie problemów w P, to czy jest jakiś znany rachunek, który może rozwiązać dokładnie problemy w P?

Edycja: moje przypuszczenie w pierwszym akapicie poniżej jest błędne! Ugo Dal Lago zwrócił mi uwagę na późniejszy artykuł Martina Hofmanna (ukazany w POPL 2002), którego nie byłem świadomy, pokazując (jako następstwo bardziej ogólnych wyników), że system z książki ATTPL jest w rzeczywistości kompletny dla ( pomimo niemożności obliczenia każdej funkcji w F P ). Ku mojemu zdziwieniu odpowiedź na główne pytanie brzmi: tak.$\mathsf P$$\mathsf{FP}$

Dotyczącą systemu masz na myśli (z książki ATTPL), jestem pewien, że nie może zdecydować każdy język w . Z pewnością nie jest w stanie obliczyć każdej funkcji w F P : jak wspomniano w uwagach do tego rozdziału, system ten został zaczerpnięty z artykułu LICS 1999 Martina Hofmanna („Typy liniowe i obliczanie wielomianu nie zwiększającego wielkości”), w którym pokazano że reprezentowalne funkcje to czas działania i nie zwiększają rozmiaru$\mathsf P$$\mathsf{FP}$, co wyklucza wiele funkcji polytime. Wydaje się również, że stanowi poważne ograniczenie rozmiaru taśmy maszyn Turinga, które można symulować w tym języku. W artykule Hofmann pokazuje, że można zakodować obliczenia przestrzeni liniowej; zgaduję, że nie będziesz w stanie zrobić dużo więcej, tj . klasa odpowiadająca temu systemowi to z grubsza problemy, które można rozwiązać jednocześnie w polityce czasowej i przestrzeni liniowej.

Jeśli chodzi o drugie pytanie, istnieje kilka -calculi, które mogą rozwiązać problemy w dokładnie P . Niektóre z nich są wymienione w uwagach do rozdziału ATTPL, do którego się odwołujesz (rozdz. 1.6): Wielopoziomowy λ- rachunek Leivanta (patrz jego praca POPL 1993 lub praca z Jean-Yves Marion "Lambda Calculus Characterizations of Poly-Time ” Fundamenta Informaticae 19 (1/2): 167-184, 1993), co jest związane z Bellantoni and Cook charakterystyki F P ; oraz λ- calculi pochodzące z lekkiej logiki liniowej Girarda ( Information and Computation , 143: 175–204, 1998) lub z miękkiej logiki liniowej Lafonta ( Theoretical Computer Science)$\lambda$$\mathsf P$$\lambda$$\mathsf{FP}$$\lambda$318 (1-2): 163-180, 2004). Systemy typów wynikające z tych dwóch ostatnich systemów logicznych i zapewniające zakończenie czasu policyjnego (wciąż ciesząc się kompletnością) można znaleźć w:

Patrick Baillot, Kazushige Terui. Rodzaje światła do obliczania czasu wielomianowego w rachunku lambda. Informacje i obliczenia 207 (1): 41–62, 2009.

Marco Gaboardi, Simona Ronchi Della Rocca. Od lekkiej logiki po przypisania typów: studium przypadku. Logic Journal of IGPL 17 (5): 499-530, 2009.

W tych dwóch artykułach znajdziesz wiele innych odniesień.

Podsumowując, pozwól mi rozwinąć uwagę Neela Krishnaswamiego. Sytuacja jest nieco subtelna. Wszystkie powyższe kalkulatory mogą być postrzegane jako ograniczenia bardziej ogólnych rachunków, w których można obliczyć znacznie więcej niż tylko funkcje polytime, np. System F. Innymi słowy, definiuje się właściwość Φ programów F programów P : string → bool taki, że:$\lambda$$\Phi$$P:\texttt{string}\rightarrow\texttt{bool}$

solidność: oznacza, że ​​język wybrany przez P jest w P ;$\Phi(P)$$P$$\mathsf P$

kompletność: dla każdego istnieje system F program P decydujący L taki, że Φ ( P ) .$L\in\mathsf P$$P$$L$$\Phi(P)$

Interesujące jest to, że właściwość wyrażona przez jest czysto składniowa, a w szczególności rozstrzygalna. Dlatego kompletność może zachowywać się wyłącznie w sensie ekstensywnym: jeśli L jest twoim ulubionym językiem w P, a jeśli P jest twoim ulubionym algorytmem decydującym o L wyrażonym w systemie F, może być tak, że Φ ( P ) nie zachowuje. Wszystko co wiem to, że istnieje jakiś inny program System F P ' decydując L i takie, że Φ ( P ' ) posiada. Niestety może się zdarzyć, że P $\Phi$$L$$\mathsf P$$P$$L$$\Phi(P)$$P'$$L$$\Phi(P')$$P'$jest znacznie więcej niż wymyślony . Rzeczywiście, kompletność została potwierdzona przez kodowanie wielomianowo taktowanych maszyn Turinga jako spełniające warunki systemu F Φ . Dlatego jedynym gwarantowanym sposobem rozwiązania L przy użyciu twojego ulubionego algorytmu jest implementacja tego algorytmu na maszynie Turinga, a następnie przetłumaczenie go w systemie F przy użyciu kodowania podanego w dowodzie kompletności (twoje własne kodowanie może nie działać!). Niezupełnie najbardziej eleganckie rozwiązanie w zakresie programowania ... Oczywiście w wielu przypadkach „naturalny” program P spełnia Φ . Jednak w wielu innych przypadkach tak nie jest: we wspomnianym powyżej dokumencie LICS 1999 Hofmann podaje rodzaj wstawiania jako przykład.$P$$\Phi$$L$$P$$\Phi$

Istnieją celowo kompletne systemy typów, które potrafią dokładnie wpisywać programy czasu polytime w szerszym języku (system F w moim przykładzie powyżej). Oczywiście są one ogólnie nierozstrzygalne. Widzieć

Ugo Dal Lago, Marco Gaboardi. Liniowe typy zależne i względna kompletność. Metody logiczne w informatyce 8 (4), 2011.