Jakie są ważne powody, by wierzyć ?

23

Jakie są ważne powody, by wierzyć $L\neq P$ ? L jest klasą algorytmów przestrzeni logów ze wskaźnikami do danych wejściowych.

Załóżmy, że L = P na chwilę. Jak wyglądałby algorytm przestrzeni logów dla problemu P-complete w jego ogólnych zarysach?

cc.complexity-theory complexity-classes

— Jumer
źródło

2

w pewnym sensie byłby to algorytm kompresji przestrzeni dla obliczenia maszyny Turinga w czasie P, który zwykle zajmuje przestrzeń P. stąd jeśli L ≠ P, to istnieje pewna „(nie) granica ściśliwości” P. możliwa konstrukcja / pytanie / kierunek badań oparty na tym kącie, kompresja sekwencji przebiegu TM

— vzn

1

patrz także cytowany tam post na blogu L / P i kintalis

— dniu

28

Wynik Mulmuleya (ze strony Mulmuleya bez paywall), że w modelu PRAM bez operacji bitowych „ $\mathsf{P} \neq \mathsf{NC}$ ". (W zwykłym modelu logicznym, w którym mieszka $\mathsf{L}$ , $\mathsf{L} \subseteq \mathsf{NC}$ .) Ten model jest na tyle silny, że wynik sugeruje dowolny algorytm $\mathsf{L}$ dla $\mathsf{P}$ -kompletny problem musiałby wyglądać zupełnie inaczej niż większość znanych algorytmów dla $\mathsf{P}$ -kompletnych problemów.

Model PRAM bez operacji bitowych jest niejednolitym, algebraicznym modelem nad $\mathbb{Z}$ (podobnym do algebraicznych drzew obliczeniowych lub modelu algebraicznego RAM Blum - Shub - Smale), w którym niejednorodny program może zależeć nie tylko od liczby liczby całkowite, ale także ich całkowita długość bitowa. W ten sposób nie jest to „czysto” model algebraiczny, ale żyje gdzieś pomiędzy algebraicznym a boolowskim. Model ten obejmuje algorytmy wieloczasowe do programowania liniowego, maksymalnego przepływu, skrótu, ważonego drzewa opinającego, najkrótszych ścieżek i innych problemów optymalizacji kombinatorycznej, algorytm przestrzeni logicznej dla izomorfizmu drzewa (patrz komentarze poniżej) oraz algorytmy do aproksymacji złożonych pierwiastków wielomianów, dlatego mówię dowolny algorytm $\mathsf{L}$ dla $\mathsf{P}$ -Kompletny problem (który, jak sugeruje twoje pytanie, większość ludzi uważa, że nie istnieje) musiałby wyglądać zupełnie inaczej niż którykolwiek z nich.

— Joshua Grochow
źródło

Jak w swoim przypuszczeniu na stronie 62 Mulmuley wiąże z przepływem minimalnym? Dlaczego musi być liniowy, a biologiczny? Hipoteza wydaje się sugerować, nie rank- liniową mapę (od odwrotnego mapy na liniową mapę 1-1 liniowy) ocenia się na zerowej zestaw może obejmować . Czy moja interpretacja jest poprawna?

S L_{m} (C)

$SL_m(C)$

L

$L$

F

$F$

k

$k$

S L_{m} (C)

$SL_m(C)$

L (n)

$L(n)$

— T ....

(Dobre pytanie, ale wydaje się nieco ortogonalne w stosunku do pytania zadawanego tutaj ...) Tak. Wszystko, co można wydajnie obliczyć w modelu PRAM bez operacji bitowych, ma małą formułę , dlatego (przez Valiant) jest rzutem det: . W szczególności iff iff .

φ

$\varphi$

φ (x) = det (F (x))

$\varphi(x) = \det(F(x))$

x \in L (n)

$x \in L(n)$

det (F (x)) = 1

$\det(F(x)) = 1$

x \in F^{- 1} (S L_{m})

$x \in F^{-1}(SL_m)$

— Joshua Grochow

jedynym założeniem jest które wydaje się być prawdą. Dość interesujące! Podobnie jak w przypadku innych takich założeń i dowodów na złożoność - czy znany jest inny sposób: jeśli to ? Nigdy nie widziałem takich konwersji w teorii złożoności, czy też takie konwersje nie są możliwe?

d e t \notin N C^{1}

$det\notin NC^{1}$

d e t \in N C^{1}

$det\in NC^1$

P = N C

$P=NC$

— T ....

@JAS: Nie rozumiem, co masz na myśli przez „jedynym założeniem jest ...”: Nie sądzę, że z tego wynika, że , jeśli tak mówiłeś ...

det \notin N C^{1} \Rightarrow P \neq N C

$\det \notin NC^1 \Rightarrow P \neq NC$

— Joshua Grochow,

1

@JAS: Przekonanie, że obsługuje przypuszczenie, ale nie implikuje przypuszczenia. Wspomina odwrotnie, że jeśli idealne dopasowanie to hipoteza jest fałszywa dla małego . Odpowiednio, jeśli hipoteza jest prawdziwa, wówczas idealne dopasowanie . Zauważ, że jest to przeciwny kierunek niż to, co mówiłeś.

d e t \notin N C^{1}

$det \notin NC^1$

\in N C^{1}

$\in NC^1$

a

$a$

\notin N C^{1}

$\notin NC^1$

— Joshua Grochow

15

Istnieje szereg prac M. Hofmanna i U. Schöppa, które formalizują intuicyjne pojęcie „typowych algorytmów przestrzeni logarytmicznej”, wykorzystując tylko stałą liczbę wskaźników do struktury danych wejściowych, jako język programowania PURPLE (czyste programy wskaźnikowe z iteracja.)

Mimo że programy PURPLE nie przechwytują wszystkich (okazało się, że nie są w stanie zdecydować o pośredniej łączności), ich rozszerzenie z liczeniem jest pokazane, aby przechwycić dużą część , ale nie problem P-zupełny Horn-SAT. Jest to pokazane w najnowszym artykule z serii: M. Hofmann, R. Ramyaa i U. Schöpp: Pure Pointer Programs and Tree Isomorphism, FOSSACS 2013. $\mathsf{L}$ $\mathsf{L}$

Wniosek wydaje się być taki, że algorytmy przestrzeni logarytmicznej dla problemów skompletowanych z muszą być bardzo nietypowe i wykraczać poza to, co można zaimplementować w PURPLE z liczeniem. $\mathsf{P}$

— Jan Johannsen
źródło

5

FIOLETOWY z liczeniem jest interesującym modelem i odpowiada mojej naiwnej intuicji algorytmów loglog. Ale nie wiem, czy ten wynik jest dobrym dowodem na : mówią nawet: „Tak więc nie można zdecydować o satysfakcji Horn w PURPLE powiększonym o niedeterminizm i liczenie, ale z tego samego powodu, że konkretny problem LOGSPACE, a mianowicie izomorfizm drzew nie może. ” Zasadniczo mówi to, że wynik naprawdę dotyczy słabości liczby PURPLE + (odpowiadającej naiwnej intuicji alg logspace), a nie słabości L ...

L \neq P

$L \neq P$

— Joshua

3

Złożoność opisowa próbowała udzielić odpowiedzi.

FO (logiczne pierwszego rzędu) z ORD (kolejność domen) i TC (przechodni końcowe) . $= L$

FO + ORD + lfp (Least punkt stały) . $= P$

Powstaje więc pytanie - czy FO + ord + TC FO + ord + LFP? $\subset$

Z drugiej strony FO + LFP (bez ord) nawet się nie liczy! Na przykład nie jest w stanie wyrazić faktu, że liczność domeny jest parzysta. Ta logika z pewnością nie może uchwycić - ale pytanie brzmi, czy może uchwycić lub ? $P$ $L$ $NL$

Zobacz na przykład http://www.cs.umass.edu/%7Eimmerman/pub/EATCScolumn.pdf

Następnie logika drugiego rzędu (SO) + róg przechwytuje P, natomiast SO + Krom przechwytuje NL. Zobacz Erich Gradel, Przechwytywanie klas złożoności przez fragmenty logiki drugiego rzędu , Theoretical Computer Science, 1992.

— Martin Seymour
źródło

3

FO + LFP bez zamówienia z pewnością nie może przechwycić , z tego samego powodu, który zacytowałeś: nie może się liczyć, nawet modulo 2.

L

$\mathsf{L}$

— Jan Johannsen

Zgodzić się. Zatem pytanie (a raczej jedno z pytań) brzmi - Czy FO + LFP (bez ord) jest ścisłym podzbiorem FO + LFP (z ord)?

— Martin Seymour

0

To nie jest tak naprawdę odpowiedź, ale jak tu opisano , uważam, że dla -kompletnego problemu powinno być możliwe zdefiniowanie pewnej „miary złożoności” w instancjach, takiej jak rozwiązanie instancji złożoności wymagałoby spacji . Jeśli prawda, oznaczałoby to pożądany rozdział; jeśli zidentyfikujemy taką miarę, wydaje się, że w zasięgu jest ograniczenie złożoności monotonicznej instancji, a to dałoby namacalny dowód na to, że jesteśmy na dobrej drodze - chociaż wykazanie, że granica niemotoniczna jest znacznie trudniejsza. $\sf{P}$ $\sf{GEN}$ $k$ $\Theta(k \log n)$

— NisaiVloot
źródło