Charakterystyka problemów, dla których istnieją algorytmy czasu podliniowego

Zastanawiałem się, czy problemy, dla których istnieją algorytmy czasu podliniowego (w wielkości wejściowej), można scharakteryzować jako posiadające określone właściwości. Obejmuje to czas podliniowy (np. Testowanie właściwości, alternatywne pojęcie przybliżenia problemów decyzyjnych), przestrzeń podliniowa (np. Algorytmy szkicowania / przesyłania strumieniowego, w których maszyna Turinga ma taśmę tylko do odczytu, podliniową przestrzeń roboczą i wyjście tylko do zapisu taśma) i pomiary podliniowe (np. rzadki odzysk / wyczuwanie ściskające). W szczególności interesuje mnie taka charakterystyka zarówno dla algorytmów testowania właściwości, jak i dla klasycznego modelu algorytmów randomizowanych i aproksymacyjnych.

Na przykład problemy, dla których istnieją rozwiązania programowania dynamicznego, wykazują optymalną podbudowę i nakładające się podproblemy; te, dla których istnieje chciwe rozwiązanie, wykazują optymalną podbudowę i strukturę matroidu. I tak dalej. Wszelkie odniesienia dotyczące tego tematu są mile widziane.

Z wyjątkiem kilku problemów, które dopuszczają deterministyczny algorytm subliniowy, prawie wszystkie algorytmy podliniowe, które widziałem, są losowe. Czy istnieje jakaś konkretna klasa złożoności związana z problemami z przyjmowaniem algorytmów podliniowych? Jeśli tak, czy ta klasa jest uwzględniona w BPP lub PCP?

cc.complexity-theory ds.algorithms complexity-classes approximation-algorithms Massimo Cafaro
źródło

czas sublinearny w jakim modelu?

Kaveh

algorytmy testowania właściwości są w ogólnych ramach tego, co chcesz, ale najpierw należy odpowiedzieć na punkt Kaveha.

Suresh Venkat

Zredagowałem swoje pytanie, dodając wymagane informacje.

Massimo Cafaro,

Transformata Fouriera wektora może być obliczona w czasie podliniowym, gdy jest (prawie)

rzadka w dziedzinie częstotliwości. Tak więc właściwością tutaj jest rzadkość. Sprawdź na przykład „Prosty i praktyczny algorytm dla rzadkiej transformacji Fouriera” autorstwa Haithama Hassanieha, Piotra Indyka, Diny Katabi i Erica Price nms.lcs.mit.edu/~dina/pub/soda12.pdf i odnośniki do nich.

k

$k$

Dimitris,

Odpowiedzi:

W przypadku zadania polegającego na ciągłym testowaniu właściwości grafów znana jest interesująca charakterystyka. Właściwość wykres jest funkcją wszystkich wykresami , a także właściwość wykres jest testować jeśli jest randomizowane algorytm , że dla wszystkich i wszystkich wykresach : $\{0,1\}$ $P$ $A$ $\varepsilon > 0$ $G$

czyta tylkokrawędzie dla niektórych funkcji $A(G)$ $g(\varepsilon)$ $G$ $g$
Jeżeli , a następnie wyjścia ` '' tak' z dużym prawdopodobieństwem (powiedzmy co najmniej ) $P(G)=1$ $A(G)$ $2/3$
Jeśli trzeba dodać lub usunąć co najmniej krawędzi , aby uzyskać tak że (to znaczy, jest daleko od właściwości ), wówczas wyprowadza '' ma „” z prawdopodobieństwem co najmniej $\varepsilon n^2$ $G$ $G'$ $P(G')=1$ $G$ $\varepsilon$ $A(G)$ $2/3$

Oznacza to, że rozróżnia wykresów, które mają i wykresy, które mają dużą odległość od edycji wykresów mających . Alon, Fischer, Newman i Shapira udowodnili, że właściwość jest testowalna w ten sposób wtedy i tylko wtedy, gdy właściwość można „zredukować” do właściwości sprawdzenia, czy wykres ma nieregularną partycję (w sensie Szemeredi) . To pokazuje, że regularność testowania jest w pewnym sensie „kompletna” do testowania. (Istnieje również jednostronna wersja błędu testowalności, patrz odnośnik). $A$ $P$ $P$ $P$ $\varepsilon$

Ryan Williams
źródło

W dziedzinie przestrzeni podliniowej nie ma wyraźnej klasy problemów, które dopuszczają rozwiązanie przestrzeni podliniowej, ale istnieją duże klasy problemów (oszacowanie momentu częstotliwości, redukcja wymiarów itp.), W których można wykazać istnienie małego „szkicu” i to prowadzi do wydajnych algorytmów.

Ale również w tej przestrzeni algorytmy są losowe i istnieją silne deterministyczne dolne granice oparte głównie na złożoności komunikacji.

Suresh Venkat
źródło