Czy występują problemy NP-zupełne z rozwiązaniami wielomianowego oczekiwanego czasu?

24

Czy są jakieś problemy z NP-zupełnością, dla których znany jest algorytm, że oczekiwany czas działania jest wielomianowy (dla pewnego rozsądnego rozkładu między instancjami)?

Jeśli nie, to czy istnieją problemy, dla których ustalono istnienie takiego algorytmu?

Czy istnienie takiego algorytmu sugeruje istnienie deterministycznego wielomianowego algorytmu czasu?

cc.complexity-theory np-hardness Steve Kroon
źródło

6

Nie do końca rozumiem, o co chodzi. Czy pytasz o średnie wyniki dla problemów trudnych dla NP, czy pytasz, czy możemy rozwiązać problemy trudne dla NP w najgorszym przypadku w oczekiwanym czasie wielomianowym?

Moritz

2

Co rozumiesz przez „oczekiwany czas działania”? Czy bierzesz pod uwagę oczekiwany losowy rozkład danych wejściowych (jak wydaje się sądzić większość odpowiedzi), czy rozkład losowych bitów używanych przez algorytm (zwykłe znaczenie dla algorytmów losowych), czy też oba?

Jeffε

@Moritz: Pytam o średnie wyniki dla problemów trudnych dla NP. Rozwiązywanie trudnych problemów NP w najgorszym przypadku w spodziewanym czasie wielomianowym wydaje mi się jeszcze silniejszym wynikiem, więc zainteresowałbym się również takimi wynikami. @JeffE Mówię o oczekiwanym czasie i pewnej dystrybucji między instancjami. Jeśli algorytm jest randomizowany, należy wziąć pod uwagę również losowe bity. Ale moje pytanie nie dotyczy przede wszystkim algorytmu losowego.

Steve Kroon

3

Prosta technika wypełniania umożliwia skonstruowanie ich na podstawie dowolnego problemu.

Załóżmy, że jest $L$ język -Complete co wymaga czasu rozwiązania. Zatem niech będzie Następniejest rozwiązywane w następujący sposób: algorytm czasu liniowego sprawdza, czy łańcuch wejściowy ma parzystą liczbę znaków, z których pierwszewynosi. Jeśli nie, to odrzuca; Rozwiązuje ono poza. Jeśli $NP$ $O(2^{n})$ $K$

K = {1^{n} x | ‖ x ‖ = n and x \in L}

$K=\{1^nx\ |\ \|x\|=n \text{ and }x\in L\}$

K

$K$

n

$n$

1^{n}

$1^n$

x \overset{?}{\in} L

$x\overset{?}{\in}L$

y \in_{R} {0, 1}^{2 n}

$y\in_R \{0,1\}^{2n}$ jest losowany równomiernie, oczekiwany czas rozwiązania to

y \overset{?}{\in} K

$y\overset{?}{\in}K$

\frac{1}{2^{2 n}} (2^{n} \cdot 2^{n} + (2^{2 n} - 2^{n}) O (n)) = 1 + (1 - \frac{1}{2^{n}}) O (n) \in O (n) .

$\frac{1}{2^{2n}}\big(2^n\cdot 2^n+(2^{2n}-2^n)O(n)\big) = 1+(1-\frac{1}{2^n})O(n)\in O(n).$

$K$ jest -Complete. Zmniejszenie z wynosi: $NP$ $L$

x \in {0, 1}^{n} \mapsto 1^{n} x

$x\in \{0,1\}^n \mapsto 1^nx$

Lieuwe Vinkhuijzen
źródło

13

Istnieje algorytm wielomianowy do znajdowania cykli hamiltonowskich na losowych wykresach, który działa asymptotycznie z takim samym prawdopodobieństwem, jak istnieje cykl hamiltonowski. Oczywiście w najgorszym przypadku problem ten jest trudny do rozwiązania.

Pokazują również, że algorytm programowania dynamicznego, który zawsze gwarantuje znalezienie cyklu hamiltonowskiego, jeśli istnieje, ma wielomianowy oczekiwany czas działania, jeśli rozkład wejściowy jest jednolicie losowy na zbiorze wszystkich wykresów wierzchołków. $n$

Odniesienie: „Algorytm znajdowania cykli Hamiltona na losowych wykresach”

Bollobas, Fenner, Frieze

http://portal.acm.org/citation.cfm?id=22145.22193

Aaron Roth
źródło

10

Jeśli chodzi o twoje ostatnie pytanie, czy istnienie dobrego algorytmu średniego przypadku oznaczałoby istnienie dobrego algorytmu najgorszego przypadku: jest to główne otwarte pytanie, które jest szczególnie interesujące dla kryptografów. Kryptografia wymaga problemów, które są średnio trudne, ale kryptografowie chcieliby oprzeć swoje konstrukcje na minimalnych założeniach, dlatego bardzo interesujące jest znalezienie problemów, w których średnia twardość przypadkowa jest prawdopodobnie równa twardości najgorszego przypadku.

Wiadomo, że w kilku problemach z siecią występuje redukcje od najgorszych do średnich przypadków. Zobacz na przykład Generowanie trudnych przypadków problemów z siecią przez Ajtai i artykuł z ankiety Micciancio.

Ian
źródło

9

$n$ $n$

Odniesienie:

Alexander D. Scott i Gregory B. Sorkin. Rozwiązywanie rzadkich przypadkowych przypadków Max Cut i Max 2-CSP w liniowym oczekiwanym czasie. Grzebień. Probab Comput, 15 (1-2), 281-315, 2006. Preprint

Serge Gaspers
źródło

2

Θ (n)

$\Theta(n)$

G (n, c / n)

$G(n,c/n)$

@ Bart: Mogłem źle zrozumieć pytanie. Twierdzę, że Max 2-CSP z liniową liczbą klauzul jest NP-trudny, ale istnieje algorytm przewidujący czas liniowy rozwiązujący ten problem w przypadkowych przypadkach.

Serge Gaspers

Zasadniczo, jeśli dobrze rozumiem twój argument, mówisz, że Max 2-CSP wyposażony w rozkład G (n, c / n) na leżących poniżej wykresach można rozwiązać w oczekiwanym czasie liniowym. Zgadzam się z Bartem, że dystrybucja nie wydaje mi się całkowicie „rozsądna” lub „naturalna”, ale myślę, że odpowiednio odpowiada na moje pytanie.

Steve Kroon

@ Steve: Zgadzam się.

Serge Gaspers

7

To nie odpowiada całkowicie na twoje pytanie, ale do badania wyników w przypadkowych przypadkach 3-SAT możesz to zobaczyć: www.math.cmu.edu/~adf/research/rand-sat-algs.pdf

Zazwyczaj trudno jest zdefiniować, co tak naprawdę oznacza „rozsądne rozproszenie”. Możesz skorzystać z tego linku, aby przeczytać więcej na ten temat w ankiecie „Bogdanov i Trevisan” w średnim czasie: http://arxiv.org/abs/cs/0606037 .

Grigorij Jarosławcew
źródło

Dzięki za linki. Niestety wyniki „z dużym prawdopodobieństwem” 3-SAT nie są wystarczająco silne (o ile widzę), aby potwierdzić moje zapytanie. Zgadzam się, że „rozsądna dystrybucja” może być owłosiona. Wolę to, jeśli rozkład nie jest oczywiście wybrany, aby „efektywna przestrzeń instancji” nie ograniczyła problemu do jednego, o którym wiadomo, że jest w P.

Steve Kroon

5

„Kolorowanie losowych wykresów w oczekiwanym czasie wielomianowym” Amin Coja-Oghlan i Anusch Taraz

$G \in G(n, p)$ $p < 1.01/n$ $O(√np)$

http://www.springerlink.com/content/87c17d4dacbrc0ma/

Joel Rybicki
źródło

Czy występują problemy NP-zupełne z rozwiązaniami wielomianowego oczekiwanego czasu?

Odpowiedzi: