Precyzja numeryczna w metodzie sumy kwadratów?

Czytałem trochę o metodzie sumy kwadratów (SOS) z badania Baraka i Steurera oraz notatek z wykładu Baraka . W obu przypadkach zamiatają pod dywan dywaniki o dokładności numerycznej.

Z mojego (co prawda ograniczonego) zrozumienia tej metody powinny być spełnione następujące warunki:

Biorąc pod uwagę dowolny układ równań wielomianowych $E$ względem zmiennych o wartościach rzeczywistych $x \in \mathbb{R}^n$ , gdzie wszystkie parametry to $O(1)$ ( $n$ , $|E|$ i stopień każdego ograniczenia), stopień - „ $2n$ ” ( $=O(1)$ ) Metoda SOS znajduje zadowalające przypisanie zmiennych lub dowodzi, że żadna nie istnieje w czasie $O(1)$ .

Moje pierwsze pytanie brzmi: czy powyższe twierdzenie jest prawdziwe (czy istnieje naiwny argument, który nie używa SOS do rozwiązania tego problemu?). Drugie pytanie dotyczy tego, gdzie mieści się dokładność numeryczna. Jeśli chcę uzyskać zadanie spełniające wszystkie ograniczenia dokładności addytywnej $\varepsilon$ , w jaki sposób środowisko wykonawcze zależy od $1/\varepsilon$ ? W szczególności, czy jest to wielomian?

Motywacją tego jest, powiedzmy, zastosowanie metody dziel i zwycięż w dużym systemie, dopóki podstawową podstawą nie będzie system wielkości $O(1)$ .

Edycja: od Barak-Steurer, wydaje się, że określenie „stopień $l$ sumy kwadratów z algorytmu” na P.9 (i ust prowadzących do niego) wszystkie określenia problemy rozwiązań ponad $\mathbb{R}$ , w rzeczywistości definicji pseudo -Dystrybucja w punkcie 2.2 powyżej $\mathbb{R}$ . Teraz widzę z Lemma 2.2, że nie ma gwarancji rozwiązania / odrzucenia w stopniu $2n$ bez zmiennych binarnych.

Więc mogę trochę zawęzić moje pytanie. Jeśli twoje zmienne nie są binarne, martw się, że sekwencja wyjść nie jest skończona (może nawet nie monotoniczna?). Pytanie brzmi: czy φ ( l ) wciąż rośnie? A jeśli tak, to jak daleko trzeba się posunąć, aby uzyskać dokładność addytywną ε ?$\varphi^{(l)}$$\varphi^{(l)}$$\varepsilon$

Pomimo tego, że prawdopodobnie niczego nie zmienia, zdarza mi się, że mój system jest spełnialna (nie ma zaprzeczenia jakimkolwiek stopniu), więc jestem naprawdę zaniepokojony jak duży musi być. Wreszcie interesuje mnie rozwiązanie teoretyczne, a nie rozwiązywanie liczbowe.$l$

Oto komentarz Boaza Baraka na ten temat:

$l$$l-1$$\epsilon$$\delta$$\delta$$\epsilon$

Myślę, że moja odpowiedź jest prawdopodobnie niewystarczająca, ale pozostaje dla kompletności (chociaż dla lepszej odpowiedzi zobacz poniższe komentarze Boaza)

$(x_i^2-1) \in E$$i \in[n]$$2n$$\mu(x)$$x$$E$

$\sum_{ x \in \{-1,1\}^n} \mu(x)$$\sum_{x\in\{-1,1\}^n} \mu(x) p^2(x)\ge0$$p$$n$

$n$$x_1 = 1, x_2=-1, x_3=1$$2^{-3}(1+x_1)(1-x_2)(1+x_3)$$\mu(x) \ge 0$$x\in\{-1,1\}^n$$\mu$$E$$\ell$$\ell$$n^{O(\ell)}$$\mu$$n^{O(n)}$$\mu$

$|E| = O(1)$$E$$O(1)$

$2n$$2n$$n$$\mod(x_i^2)$$n$

Na przykład, można rozważyć zastąpienie wszystkich zmiennych binarnych zmiennej 4-symbolowego, np włączając . Następnie musiałbyś mieć pseudo oczekiwanie na stopień , aby zagwarantować odzyskanie rozkładu między rozwiązaniami.$(x_i^2-1)(x_i^2-4) \in E$$4n$

Teraz, dla teoretycznych gwarancji, wydaje się, że przybliżenie korzenia systemu wielomianów jest również znane jako 17. problem Smale'a i najwyraźniej istnieje losowy algorytm wielomianowy (Las Vegas), który to rozwiązuje - patrz http://arxiv.org /pdf/1211.1528v1.pdf . Zauważ, że wydaje się, że dzieje się tak w modelu Blum-Shub-Smale, więc rzeczywiste operacje są prymitywne. Nie jestem pewien, czy daje to gwarancję, której potrzebujesz.