Każdy problem algorytmiczny ma złożoność czasową zdominowaną przez liczenie?

To, co nazywam liczeniem, to problem polegający na znalezieniu liczby rozwiązań funkcji. Dokładniej, biorąc pod uwagę funkcję $f:N\to \{0,1\}$ (niekoniecznie czarna skrzynka), przybliżone $\#\{x\in N\mid f(x)= 1\}= |f^{-1}(1)|$.

Szukam problemów algorytmicznych, które wymagają pewnego rodzaju zliczania i na które złożoność czasu ma duży wpływ ten podstawowy problem zliczania.

Oczywiście szukam problemów, które same się nie liczą. Byłoby bardzo mile widziane, gdybyś mógł dostarczyć dokumentację dotyczącą tych problemów.

Jest to kontynuacja odpowiedzi Suresha. Jak mówi, istnieje wiele problemów konstrukcyjnych w geometrii obliczeniowej, w których złożoność wyniku jest trywialną dolną granicą czasu działania dowolnego algorytmu. Na przykład: płaskie układy linii, trójwymiarowe diagramy Voronoi i płaskie wykresy widoczności mają kombinatoryczną złożoność w najgorszym przypadku, więc każdy algorytm konstruujący te obiekty w najgorszym przypadku wymaga czasu Ω ( n 2 ) . (Istnieją algorytmy czasu O ( n 2 ) dla wszystkich trzech tych problemów).$\Theta(n^2)$$\Omega(n^2)$$O(n^2)$

Przypuszcza się jednak, że podobne ograniczenia dotyczą również problemów decyzyjnych . Na przykład, biorąc pod uwagę zestaw n linii na płaszczyźnie, jak łatwo można sprawdzić, czy jakieś trzy linie przechodzą przez wspólny punkt? Cóż, możesz zbudować układ linii (wykres płaski zdefiniowany przez ich punkty przecięcia i odcinki między nimi), ale zajmuje to czasu. Jednym z głównych rezultatów mojej pracy doktorskiej było to, że w ramach ograniczonego, ale naturalnego modelu drzewa decyzyjnego obliczeń wymagany jest czas Ω ( n 2 ) na wykrycie potrójnych skrzyżowań. Intuicyjnie możemy musi wyliczyć wszystkie$\Theta(n^2)$$\Omega(n^2)$$\binom{n}{2}$ punktów przecięcia i poszukaj duplikatów.

Podobnie istnieje zbiór liczb, w których potrójne elementy sumują się do zera. W związku z tym, każdy algorytm (modelowany pewnej klasy drzew decyzyjnych) w celu sprawdzenia, czy dany zestaw składa się z trzech elementów, suma zero wymaga czasu . (Możliwe jest golenie niektórych dzienników przez równoległość na poziomie bitów, ale cokolwiek.)Ω ( n 2 )$\Theta(n^2)$$\Omega(n^2)$

Innym przykładem, również z mojej tezy, jest problem Hopcroft: Biorąc pod uwagę punktów i linii na płaszczyźnie, czy dowolny punkt zawiera dowolną linię. Najgorszą liczbą przypadków linii punktowych jest . Udowodniłem, że w ograniczonym (ale wciąż naturalnym) modelu obliczeń, jest potrzebny czas, aby ustalić, czy występuje choć jeden przypadek linii punktowej. Intuicyjnie musimy wyliczyć wszystkie pobliżu przypadków i sprawdzić każdy z nich, aby zobaczyć, czy to naprawdę przypadek.n Θ ( n 4 / 3 ) Ω ( n 4 / 3 ) Θ ( n 4 / 3$n$$n$$\Theta(n^{4/3})$$\Omega(n^{4/3})$$\Theta(n^{4/3})$

Formalnie te dolne granice są wciąż tylko przypuszczeniami, ponieważ wymagają one ograniczonych modeli obliczeniowych, które specjalizują się w danym problemie, szczególnie w przypadku problemu Hopcrofta). Jednak udowodnienie dolnych granic dla tych problemów w modelu pamięci RAM jest prawdopodobnie tak samo trudne jak jakikolwiek inny problem dolnej granicy (tj. Nie mamy pojęcia) - patrz artykuł SODA 2010 autorstwa Patrascu i Williamsa dotyczący uogólnień 3SUM do czasu wykładniczego hipoteza.

Nie jestem do końca pewien, czy to masz na myśli, ale istnieje szereg problemów, które nie wydają się liczeniem problemów, jednak najlepszym sposobem, w jaki wiemy, jak je rozwiązać, jest policzenie obiektów. Jednym z takich problemów jest wykrycie, czy wykres zawiera trójkąt. Najszybszym znanym algorytmem jest obliczenie śladu kostki macierzy przyległości, która jest 6 razy większa niż liczba trójkątów na (niekierowanym) wykresie. Zajmuje to czas O ( ) przy użyciu algorytmu mnożenia macierzy Coppersmitha-Winograda. Zostało to zauważone po raz pierwszy przez Itai i Rodeha w 1978 r. Podobnie najlepszym sposobem na wykrycie kliki typu k jest kliknięcie liczba k-klików, również poprzez mnożenie macierzy.$|V|^{2.376}$

Valiant udowodnił, że problem znalezienia stałej macierzy jest kompletny dla #P . Zobacz stronę wikipedii na ten temat. #P to klasa złożoności odpowiadająca zliczeniu liczby ścieżek akceptacji maszyny NP.

Dwustronne Planar (i rodzaj logu) Idealne dopasowanie to problem, w którym algorytm Kastelyn do zliczania dopasowań planarnych (rozszerzony przez Galluccio i Loebl i zrównoleglony przez Kulkarni, Mahajan i Vardarajan) odgrywa ważną rolę nawet w wyszukiwawczej wersji problemu. Wszystkie odpowiednie odniesienia można znaleźć w następującym artykule:

Kilka doskonałych dopasowań i idealne dopasowania w połowie integralne w NC. Raghav Kulkarni, Meena Mahajan i Kasturi R. Varadarajan. Chicago Journal of Theoretical Computer Science, tom 2008 Artykuł 4.

Przyjmę „pod wielkim wpływem” raczej jako miękkie ograniczenie niż jako redukcję. W tym sensie WIELE problemów w geometrii obliczeniowej ma czasy działania ograniczone przez pewną kombinatoryczną strukturę leżącą u ich podstaw. na przykład złożoność obliczania układu kształtów jest bezpośrednio związana z wewnętrzną złożonością takich układów.

Innym, aktualnym przykładem tego jest to, że różne problemy z dopasowaniem wzoru punktowego mają czas przebiegu, który sprowadza się do oszacowania wielkości, takich jak liczba powtórzonych odległości w zestawie punktów i tak dalej.

Nie jestem pewien, czy tego właśnie szukałeś, ale przejścia fazowe problemów NP-Complete w dużej mierze opierają się na argumentach probabilistycznych, które są kolejną formą liczenia.

LLL został wykorzystany do rozwiązania niektórych problemów z podzbiorem „niskiej gęstości”, których powodzenie zależy od istniejących wektorów kratowych o wysokim prawdopodobieństwie, które spełniają kryteria bycia rozwiązaniem sumy podzbioru. Ankieta Propagacja opiera się na strukturze przestrzeni rozwiązań (i liczbie rozwiązań, gdy naprawia zmienne), aby znaleźć rozwiązania w pobliżu progu krytycznego.

Borgs, Chayes i Pittel prawie całkowicie scharakteryzowali przemianę fazową (jednolitego) problemu partycji liczb losowych, a tym samym scharakteryzowali, ile rozwiązań można oczekiwać dla danej (losowej) instancji problemu partycji liczbowej.