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

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.

cc.complexity-theory complexity-classes turing-machines lambda-calculus Simplex
źródło

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:

Maszyny Turinga i $\lambda$ rachunek są równoważne tylko z funkcjami $\mathbb{N} \rightarrow \mathbb{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 $\lambda$ rachunku w celu uzasadnienia złożoności, jest to, że naiwne użycie $\lambda$ rachunku powoduje nierealistyczne miary złożoności, ponieważ można swobodnie kopiować terminy (o dowolnej wielkości) w pojedynczych krokach redukcji $\beta$ , np. $(\lambda x.xxx)M \rightarrow MMM.$ Innymi słowy, pojedyncze kroki redukcji w $\lambda$ -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 $\lambda$ 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$ , $NP$ i $EXP$ można nadać naturalny preparat $\lambda$ rachunek różniczkowy. Ale mniejsze klasy, takie jak $O(n^2)$ lub $O(n \, log\, n)$ nie można przedstawić za pomocą technik Accattoli / Dal Lago.

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

Martin Berger
źródło

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

, 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

taki, że

λ T I M E (f (n))

$\lambda TIME(f(n))$

λ

$\lambda$

f (n)

$f(n)$

β

$\beta$

p

$p$

λ T I M E (f (n)) = T I M E (p (f (n))

$\lambda TIME(f(n))=TIME(p(f(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 I M E (n^{2}) = T I M E (n^{2})

$\lambda TIME(n^2) = TIME(n^2)$

Martin Berger,

Dobra, widzę. Właściwie sądzę, że

: klasy złożoności takie jak

lub

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 I M E (n^{2}) \neq T I M E (n^{2})

$\lambda TIME(n^2)\neq TIME(n^2)$

T I M E (n^{2})

$TIME(n^2)$

T I M E (n \log n)

$TIME(n\log n)$

Damiano Mazza

@DamianoMazza Zgadzam się, podobnie do wielkości wybranego alfabetu. Jednak algorytm działa w

-tape maszyny może być symulowana

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ą.

f (n)

$f(n)$

n

$n$

5 k f^{2} (n)

$5kf^2(n)$

Martin Berger,

@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,

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 $\mu$ $\lambda$ .

Istnieją charakterystyki (przynajmniej) za pomocą rachunku. $\mathsf{FP}$ $\lambda$

Bruno
źródło

Nie wiem, czy to (częściowo) odpowiada na twoje pytanie, ale rzeczywiście istnieją alternatywne charakterystyki klas złożoności (zwłaszcza $\mathbb{P}$ i $\mathbb{NP}$ ) 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 $\mathbb{P}$ vs $\mathbb{NP}$ 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