NP kompletność nad rzeczywistością

Ostatnio studiuję model obliczeniowy BSS (por. Na przykład złożoność i obliczenia rzeczywiste; Blum, Cucker, Shub, Smale).

Na Real , widoczne jest, że biorąc pod uwagę system wielomianu f 1 , ⋯ , f m ∈ R [ x 1 , ⋯ , x n ] Istnienie zer jest N P R -Complete. Zastanawiam się jednak, czy te f są wielomianami tylko współczynnikami całkowitymi, tj. F 1 , ⋯ , f m ∈ Z [ x 1 , ⋯ , x n$R$$f_1,\cdots, f_m\in R[x_1, \cdots, x_n]$$NP_R$$f$$f_1,\cdots, f_m\in Z[x_1, \cdots, x_n]$, czy nadal występuje problem twardy? (jest oczywiście w N P R ).$NP_R$$NP_R$

Podejrzewam, że tak, ale czy istnieje prosty dowód?

Myślę, że odpowiedź brzmi „ nie” , zakładając, że (wydaje mi się, że podam poniżej dowód, ale jest wystarczająco dużo potencjalnie nikczemnych kwestii definicyjnych, aby zachować ostrożność w odniesieniu do moich roszczeń).$\mathsf{P}_{\mathbb{R}} \neq \mathsf{NP}_{\mathbb{R}}$

Dowód, że odpowiedź nie jest zakładająca $\mathsf{P}_\mathbb{R} \neq \mathsf{NP}_{\mathbb{R}}$ : W rzeczywistości uważam, że następujące mocniejsze stwierdzenie zawiera:

Lemat: Dla każdej decyzji BSS problemów nad R , jeśli L poli czasie BSS R redukuje się do problemu na wejściach całkowitą, a następnie L ∈ P R .$L$$\mathbb{R}$$L$$_{\mathbb{R}}$$L \in \mathsf{P}_\mathbb{R}$

Dowód lematu Przypuśćmy było wielomianem czasie BSS R obniżenie od L do problemu z całkowitych wejściowych, ponieważ przez maszynę M . W przypadku danych wejściowych składających się z n parametrów rzeczywistych rozwiń obliczenia M w drzewie obliczeń algebraicznych. Istnieje tylko skończona liczba liści, a wynikiem dla każdego liścia jest pojedyncza racjonalna funkcja w parametrach wejściowych. Aby racjonalna funkcja rzeczywistych danych wejściowych zawsze generowała wartość całkowitą, musi być funkcją stałą, a zatem nie może zależeć od danych wejściowych. Jednak to, która stała funkcja jest stosowana na każdym liściu, może oczywiście zależeć od gałęzi. Ponieważ jednak M jest maszyną jednolitą, może istnieć tylko O$_{\mathbb{R}}$$L$$M$$n$$M$$M$ węzły wyjściowe, a zatem tylkowartości wyjściowe O ( 1 ) . Zatem M może być trywialnie zmodyfikowany, aby faktycznie decydować L w czasie wielomianowym. CO BYŁO DO OKAZANIA$O(1)$$O(1)$$M$$L$

Teraz weź aby być realną wykonalnością prawdziwych wielomianów. Jeśli P R ≠ N P R , to L ∉ P R , a przez Lemat, nie ma redukcji od L do jakiegokolwiek problemu na wejściowych liczbach całkowitych (w szczególności do rzeczywistej wykonalności wielomianów całkowitych ).$L$$\mathsf{P}_{\mathbb{R}} \neq \mathsf{NP}_{\mathbb{R}}$$L \notin \mathsf{P}_{\mathbb{R}}$$L$

Obiecujesz problem z problemem? : Innym potencjalnym problemem związanym z tym pytaniem jest to, że rzeczywista wykonalność wielomianów całkowitych może nie występować w , ale tylko w jej obiecanej wersji. Problem polega na tym, że sprawdzenie, czy dane wejściowe (takie jak współczynnik wielomianu f i ) jest liczbą całkowitą, wymaga czasu zależnego od wielkości x , natomiast zestaw instancji (wszystkie instancje, nie tylko instancje tak) dla N P R problem decyzji powinna być decyzyjny w P R , to jednak ten sposób, że następuje wielomianu czasu w szeregu parametrów$\mathsf{NP}_{\mathbb{R}}$$f_i$$x$$\mathsf{NP}_{\mathbb{R}}$$\mathsf{P}_\mathbb{R}$, a nie ich wielkości. Sądzę, że jest to ściśle związane z faktem, że liczb całkowitych nie można zdefiniować pierwszego rzędu w rzeczywistości. (Zasadniczo najlepiej BSS R może -machine zrobić aby sprawdzić, czy sygnał wejściowy x jest liczbą całkowitą jest obliczenie część całkowitą x obliczając uprawnienia 2 i robi „przeszukiwanie binarne.” Kiedy to obliczane część całkowitą x , to sprawdza czy jest równa x ). Tak więc myślę że probleam rzeczywistej możliwości całkowite równań w P r o m i e e N p R , ale prawdopodobnie nie jest w N$_{\mathbb{R}}$$x$$x$$2$$x$$x$$\mathsf{PromiseNP}_{\mathbb{R}}$ (lub przynajmniej wydaje się nieistotne, aby udowodnić, że jest w N P R ).$\mathsf{NP}_{\mathbb{R}}$$\mathsf{NP}_{\mathbb{R}}$