Dokładne algorytmy czasu wykładniczego dla programowania 0-1

Czy są znane algorytmy dla następującego problemu, które pokonały naiwny algorytm?

Dane wejściowe: system o nierówności liniowych.$Ax \le b$$m$

Wynik: wykonalne rozwiązanie jeśli takie istnieje.$x^*\in \{0,1 \}^n$

Załóżmy, że i mają wpisy liczb całkowitych. Interesują mnie granice najgorszego przypadku.$A$$b$

Jeśli jest superliniowe, taki algorytm obaliłby hipotezę silnego czasu wykładniczego, ponieważ formuły w spójnej postaci normalnej są szczególnym przypadkiem programowania 0-1, a lemat sparsyfikacyjny pozwala nam zredukować -SAT do CNF-SAT na liniowo wielu klauzulach .$m$$k$

Istnieje jednak algorytm związany z Impagliazzo, Paturi i mną, który może rozwiązać taki system nierówności, jeśli liczba drutów, tj. Liczba niezerowych współczynników w jest liniowa. W szczególności, jeśli liczba drutów wynosi , algorytm działa w czasie , gdzie s = 1c n 2 ( 1 - s ) $A$$cn$$2^{(1-s)n}$ .$s=\frac1{c^{O(c^2)}}$

Jeśli jest wystarczająco małe, możesz zrobić lepiej niż naiwny algorytm, tj. Lepiej niż 2 n razy. Tutaj „wystarczająco mały” oznacza, że m jest mniejsze niż coś takiego jak n / lg n . Czas działania będzie nadal wykładniczy - np. Może być 2 n / 2 - ale będzie szybszy niż naiwny algorytm.$m$$2^n$$m$$n/\lg n$$2^{n/2}$

Nawiasem mówiąc, wygląda na to, że pozwala nam to rozwiązać problem szybciej niż czasu w niektórych przypadkach, gdy macierz A ma superliniową liczbę wpisów. Nie wiem, jak to zrównoważyć z inną podaną tutaj odpowiedzią. W związku z tym należy dokładnie sprawdzić moją odpowiedź: może to wskazywać, że gdzieś popełniłem poważny błąd.$2^n$$A$

Podstawowe podejście: napisz , gdzie x 0 zawiera pierwsze n / 2 składowe x, a x 1 zawiera ostatnie n / 2 składowe; podobnie = ( 0 , 1 ) , w którym 0 ma lewe n / 2 kolumny A oraz A 1 prawo $x=(x_0,x_1)$$x_0$$n/2$$x$$x_1$$n/2$$A=(A_0,A_1)$$A_0$$n/2$$A$$A_1$ kolumny. Teraz A x ≤ b można ponownie zapisać w formularzu$n/2$$Ax \le b$

lub równoważnie

Wymień wszystkie możliwości dla A 0 x 0 i niech S oznacza zbiór możliwych wartości, tj.$2^{n/2}$$A_0 x_0$$S$

Podobnie wyliczyć zestaw wszystkich możliwości 2 n / 2 dla b - A 1 x 1 , tj.$T$$2^{n/2}$$b - A_1 x_1$

Teraz problem się pojawia

Biorąc pod uwagę zbiory o wielkości 2 n / 2 , czy istnieją s ∈ S i t ∈ T takie, że s ≤ t ?$S,T \subseteq \mathbb{Z}^{m}$$2^{n/2}$$s\in S$$t \in T$$s\le t$

(Tutaj przyjmuje się punktowo, tzn. Wymagamy, aby s i ≤ t i dla wszystkich i .)$\le$$s_i \le t_i$$i$

Ten ostatni problem jest omawiany na CS.StackExchange i najwyraźniej istnieje dla niego algorytm działający w czasie . Jeśli m jest wystarczająco małe (powiedzmy, mniejsze niż n / lg n ), oznacza to, że całkowity czas pracy będzie mniejszy niż 2 n , zgodnie z życzeniem.$O(2^{n/2} (n/2)^{m-1})$$m$$n/\lg n$$2^n$

Aby ten wynik brzmiał bardziej realistycznie, oto bardzo prymitywna intuicja. Jeśli weźmiemy ekstremalny przypadek, w którym , oczywiście można to szybko rozwiązać. (W rzeczywistości istnieje znacznie prostszy algorytm dla specjalnego przypadku, w którym m = 1 : niech x i = 1, jeśli A 1 , i ≤ 0 , w przeciwnym razie x i = 0 ; teraz, jeśli istnieje jakieś możliwe rozwiązanie, to ten x będzie jeden.)$m=1$$m=1$$x_i=1$$A_{1,i}\le 0$$x_i=0$$x$