Jak bardzo wyrocznia SAT pomogłaby przyspieszyć algorytmy wielomianowe?

23

Dostęp do wyroczni zapewniłby duże, super-wielomianowe przyspieszenie wszystkiego w (zakładając, że zestaw nie jest pusty). Nie jest jednak jasne, ile skorzystałby z tego dostępu do wyroczni. Oczywiście przyspieszenie w nie może być wielomianowe, ale nadal może być wielomianowe. Na przykład, czy moglibyśmy znaleźć najkrótszą ścieżkę szybciej z wyrocznią niż bez niej? Co powiesz na bardziej złożone zadania, takie jak minimalizacja funkcji podmodularnych lub programowanie liniowe? Czy skorzystaliby z (lub innych naturalnych problemów w )? $SAT$ ${\bf NP}-{\bf P}$ $\bf P$ $\bf P$ $SAT$ $\bf P$ $SAT$ wyrocznia?

Mówiąc bardziej ogólnie, jeśli możemy wybrać jakikolwiek problem w i użyć do tego wyroczni, to który z problemów w mógłby zauważyć przyspieszenie? ${\bf NP}-{\bf P}$ $\bf P$

cc.complexity-theory np np-complete

— Andras Farago
źródło

2

Jak szybka jest wyrocznia? Jeśli zajmie to czas

, można przyspieszyć więcej problemów niż czas

, gdzie

jest wielkością formuły SAT.

O (s)

$O(s)$

O (s^{5})

$O(s^5)$

s

$s$

— Peter Shor

2

@PeterShor Zakładam, że wyrocznia, po otrzymaniu formuły SAT jako zapytania, zwraca odpowiedź TAK lub NIE, co oznacza, czy formuła jest zadowalająca, czy nie, w jednym kroku (stały czas). Jest to niezależne od wielkości formuły. Oczywiście formuła musi zostać skonstruowana w celu uzyskania odpowiedzi. Ten czas budowy nie jest niezależny od wielkości formuły i zależy również od problemu, które formuły należy zapytać. Ale po zbudowaniu formuły otrzymanie odpowiedzi jest liczone jako pojedynczy krok dla dowolnej formuły.

— Andras Farago,

3

Jeśli zamiast wyroczni SAT zezwoliłeś na wyrocznię

, możesz użyć jej do znalezienia minimalnych obwodów dla dowolnego problemu. Dałoby to prawie optymalny zamortyzowany koszt dla dowolnego problemu (powodem, dla którego jest on amortyzowany tylko dlatego, że jeśli użyjesz go tylko raz, to rozmiar zapisanej przez ciebie formuły

jest zasadniczo czasem działania twojego pierwotnego wielozakresowego czasu pracy algorytm - ale po tym kroku masz optymalny obwód dla wszystkich przypadków wielkości

).

Σ_{2} S A T

$\Sigma_2 SAT$

Σ_{2} S A T

$\Sigma_2 SAT$

\leq n

$\leq n$

— Joshua Grochow

@JoshuaGrochow Twój komentarz jest bardzo interesujący! Byłoby wspaniale widzieć to jako odpowiedź, zawierającą więcej szczegółów.

— Andras Farago,

15

W rzeczywistości akceptacja niedeterministycznych maszyn Turinga w czasie oznacza - czas redukowalny do SAT (konstrukcja odbywa się poprzez nieprzewidywalną symulację, patrz Arora-Barak), więc zazwyczaj za każdym razem, gdy niedeterministyczna maszyna jest znacznie szybsza niż deterministyczna , zobaczymy przynajmniej trochę przyspieszenia z wyrocznią SAT. $t$ $O(t \log t)$

Mówiąc ściślej, przychodzi na myśl testowanie pierwotności, ponieważ najlepszy wariant algorytmu AKS wydaje się testować pierwotność liczby bitowej w czasie $n$ . Ale jeśli pójdziemy „starą szkołą”, Pratt dał niedeterministyczną TM, aby zdecydować o pierwszeństwie w czasie $O(n^6 \; \text{polylog}\; n)$ . Akceptację tej maszyny można zmniejszyć (deterministycznie) w $O(n^3 \; \text{polylog}\; n)$ czas na wystąpienie SAT. $O(n^3 \; \text{polylog}\; n)$

Problem 3SUM może być kolejnym przykładem, ponieważ wydaje się, że można odgadnąć rozwiązanie i sprawdzić je w czasie subkwadratowym, a następnie akceptację takiej maszyny można zredukować do SAT w czasie subkwadratowym.

— Joe Bebel
źródło

7

Mówiąc bardziej ogólnie, jeśli możemy wybrać jakikolwiek problem w NP-P i użyć do tego wyroczni, to który z problemów w P mógłby zauważyć przyspieszenie?

To pytanie staje się bardziej bezpośrednie w reprezentacji i czasie potrzebnym do zredukowania jednego problemu do drugiego ....

Główną odpowiedzią, o której myślę, jest wyrocznia w zakresie programowania liczb całkowitych / programowania liniowego. Wersja decyzyjna tego problemu jest NP-kompletna. Istnieje trywialna „redukcja” z programowania liniowego, ponieważ jest to szczególny przypadek. Ale wyrocznia dla samego programowania liniowego (nie mówiąc już o ILP) przyspiesza wiele problemów, które można natychmiast rozwiązać dzięki programowaniu liniowemu. Można je zredukować w czasie liniowym, przepisując problem jako LP. Na przykład najkrótsze ścieżki i inne problemy z przepływem, dopasowania.

Ale nie sądzę, że ILP jest jedyną metodą, prawdopodobnie ludzie nie myśleli zbyt wiele o np. Skróceniu najkrótszej ścieżki do TSP itp.

— usul
źródło

3

$SAT$ $\Sigma_2 SAT$ $\mathsf{P}$ $\Sigma_2 SAT$ $\leq n$ .

— Joshua Grochow
źródło

N P^{N P}

$NP^{NP}$

N P

$NP$

P

$P$

N P^{N P} \neq N P

$NP^{NP}\neq NP$

P H

$PH$

P

$P$

P

$P$

N P

$NP$

N P^{N P}

$NP^{NP}$

1

P

$\mathsf{P}$

P H

$\mathsf{PH}$

k

$k$

k + 2

$k+2$