Wyjaśnienie klas P i NP za pomocą rachunku lambda

36

We wstępie i wyjaśnieniach klasy złożoności P i NP często podawane przez maszynę Turinga. Jednym z modeli obliczeń jest rachunek lambda. Rozumiem, że wszystkie modele obliczeń są równoważne (i jeśli możemy wprowadzić coś w kategoriach maszyny Turinga, możemy wprowadzić to w kategoriach dowolnego modelu obliczeń), ale nigdy nie widziałem wyjaśnienia klasy złożoności P i NP za pomocą rachunku lambda . Czy ktoś może wyjaśnić pojęcia klasy złożoności P i NP bez maszyny Turinga i tylko za pomocą rachunku lambda jako modelu obliczeniowego.

Simplex
źródło
5
Ich moc obliczeniowa jest równoważna tylko dla funkcji nad liczbami naturalnymi, a nie dla wyższych typów lub innych ustawień.
Kaveh
Kompletność Turinga jest czasem bardziej teoretyczną koncepcją pokazującą połączenie, ale częściej stosowane „konwersje” między kompletnymi systemami TM nie zawsze są faktycznie przeprowadzane w praktyce, to znaczy czasami więcej o dowodach na istnienie ...
vzn

Odpowiedzi:

40

Maszyny Turinga i λ rachunek są równoważne tylko z funkcjami N.N. które mogą zdefiniować.

Z punktu widzenia złożoności obliczeniowej zachowują się inaczej. Głównym powodem, dla którego ludzie używają maszyn Turinga, a nie λ rachunku w celu uzasadnienia złożoności, jest to, że naiwne użycie λ rachunku powoduje nierealistyczne miary złożoności, ponieważ można swobodnie kopiować terminy (o dowolnej wielkości) w pojedynczych krokach redukcji β , np. (λx.xxx)M.M.M.M..Innymi słowy, pojedyncze kroki redukcji w λ-kalkulus to kiepski model kosztów. Natomiast pojedyncze kroki redukcji maszyny Turinga działają świetnie (w sensie dobrego przewidywania czasu działania programu w świecie rzeczywistym).

Nie wiadomo, jak w pełni odzyskać konwencjonalną teorię złożoności opartą na maszynie Turinga w λ rachunku. W ostatnim (2014) przełomowym Accattoli i Dal Lago udało się wykazać, że dużym klasom złożoności czasowej, takim jak P. , N.P. i miXP. można nadać naturalny preparat λ rachunek różniczkowy. Ale mniejsze klasy, takie jak O(n2)) lub O(nlosoln) nie można przedstawić za pomocą technik Accattoli / Dal Lago.

Jak odzyskać konwencjonalną złożoność przestrzeni za pomocą λ rachunek jest nieznany.

Martin Berger
źródło
4
Czuję potrzebę wyjaśnienia tutaj: nie ma specjalnej „techniki” stosowanej przez Accattoli i Dal Lago do „prezentacji” zajęć czasowych. Prezentacja jest „naiwna”: zdefiniuj jako klasę języków rozstrzygalną przez λ- term w etapach redukcji f ( n ) β , w ramach dowolnej standardowej strategii redukcji ( np. Skrajnie lewy -outermost). Accattoli i Dal Lago wykazali, stosując techniki pochodzące z logiki liniowej, że istnieje wielomian p taki, że λ T I M E ( fλT.jaM.mi(fa(n))λfa(n) βp .λT.jaM.mi(fa(n))=T.jaM.mi(p(fa(n))
Damiano Mazza
@DamianoMazza Tak, właśnie tak, miałem na myśli to, że nie sądzę, że techniki użyte do pokazania tego wyniku mogą być użyte do pokazania np. . λT.jaM.mi(n2))=T.jaM.mi(n2))
Martin Berger,
3
Dobra, widzę. Właściwie sądzę, że : klasy złożoności takie jak T I M E ( n 2 ) lub T I M E ( n log n ) nie są solidne , nie można oczekiwać, że będą stabilne przy zmianach modelu obliczeniowego (dzieje się to notorycznie, nawet jeśli trzymamy się maszyn Turinga, np. pojedyncza taśma vs. wielopasmowa).λT.jaM.mi(n2))T.jaM.mi(n2))T.jaM.mi(n2))T.jaM.mi(nlogn)
Damiano Mazza
3
@DamianoMazza Zgadzam się, podobnie do wielkości wybranego alfabetu. Jednak algorytm działa w na n -tape maszyny może być symulowana 5 k f 2 ( n ), na maszynie 1, taśmy, niewielką blowup kwadratowego. Jaki jest wybuch obecnego tłumaczenia Accattoli i Dal Lago? Nie pamiętam, czy to wyraźnie stwierdzają. fa(n)n5kfa2)(n)
Martin Berger,
1
@Jake Cytowany artykuł omawia normalizację beta (patrz strona druga). Podobne wyniki były już znane w przypadku innych form redukcji, takich jak słaba redukcja (tj. Call-by-value) - patrz Dal Lago i Martini, 2008 (omówione w tym dokumencie oraz w cstheory.stackexchange.com/a/397/989 ).
Blaisorblade,
12

Wklejam część odpowiedzi, którą napisałem na inne pytanie :

Implikowana złożoność obliczeniowa ma na celu scharakteryzowanie klas złożoności za pomocą dedykowanych języków. Pierwsze wyniki, takie jak Twierdzenie Bellantoniego-Cooka, podano w kategoriach -funkcji rekurencyjnych, ale nowsze wyniki wykorzystują słownictwo i techniki λ- kalkulatora. Zobacz krótkie wprowadzenie do niejawnej złożoności obliczeniowej, aby uzyskać więcej wskazówek i wskazówek na temat warsztatów DICEμλ .

Istnieją charakterystyki (przynajmniej) za pomocą λ- rachunku.FPλ

Bruno
źródło
5

Nie wiem, czy to (częściowo) odpowiada na twoje pytanie, ale rzeczywiście istnieją alternatywne charakterystyki klas złożoności (zwłaszcza P. i N.P. ) pod względem logiki (logika pierwszego rzędu, logika drugiego rzędu itp.).

Na przykład praca z R. Fagina (et al.) W tym obszarze jest znaczący (i imo może zapewnić wgląd związane z P. vs N.P. emisji i stosunków z opisowy i algorytmicznej złożoności)

Niektóre dalsze charakterystyki klas złożoności obliczeniowej pod względem złożoności algorytmicznej (Kolmogorov-Solomonov) można znaleźć (na przykład) tutaj i tutaj .

Nikos M.
źródło