Czy istnieją ustalone klasy złożoności z liczbami rzeczywistymi?

Niedawno student poprosił mnie o sprawdzenie dla nich dowodu twardości NP. Dokonali redukcji zgodnie z:

Zmniejszam ten problem $P'$ którym wiadomo, że jest NP-kompletny do mojego problemu $P$ (z redukcją wielokrotnego wielokrotności jeden), więc $P$ jest NP-twardy.

Moja odpowiedź brzmiała w zasadzie:

Ponieważ $P$ ma instancje z wartościami z $\mathbb{R}$ , nie można go obliczyć Turinga, więc można pominąć redukcję.

Chociaż formalnie jest to prawda, nie sądzę, aby takie podejście było wnikliwe: z pewnością chcielibyśmy uchwycić „nieodłączną złożoność” problemu decyzyjnego (lub optymalizacji) o wartości rzeczywistej, ignorując ograniczenia, które napotykamy w radzeniu sobie z prawdziwymi liczby; badanie tych problemów jest na inny dzień.

Oczywiście nie zawsze jest to tak proste, jak powiedzenie: „dyskretna wersja podzbioru sumy jest NP-zupełna, więc wersja ciągła również jest„ NP-trudna ”. W tym przypadku redukcja jest łatwa, ale znane są przypadki łatwiejszej ciągłej wersji, np. Programowanie liniowe vs. całkowite.

Przyszło mi do głowy, że model RAM naturalnie rozciąga się na liczby rzeczywiste; niech każdy rejestr zapisze rzeczywistą liczbę i odpowiednio rozszerzy podstawowe operacje. Model jednolitego kosztu nadal ma sens - tak samo jak w przypadku dyskretnym - podczas gdy model logarytmiczny nie.

Moje pytanie sprowadza się zatem do: czy istnieją ustalone pojęcia złożoności problemów o wartości rzeczywistej? Jak odnoszą się one do „standardowych” klas dyskretnych?

^{Wyszukiwania w Google przynoszą pewne wyniki, np. To , ale nie mam sposobu, aby powiedzieć, co zostało ustalone i / lub przydatne, a co nie.}

Tak. Tam są.

Istnieje inny model rzeczywistej pamięci RAM / BSS wymieniony w drugiej odpowiedzi. Model ma pewne problemy, a AFAIK nie prowadzi zbyt wielu badań. Prawdopodobnie nie jest to realistyczny model obliczeń .

Bardziej aktywne pojęcie rzeczywistej obliczalności to model obliczeń wyższego typu. Podstawową ideą jest zdefiniowanie złożoności dla funkcji wyższego typu, a następnie użycie funkcji wyższego typu do przedstawienia liczb rzeczywistych.

Badanie złożoności funkcji wyższego typu sięga co najmniej do [1]. Aby zapoznać się z ostatnimi pracami, sprawdź dokumenty Akitoshi Kawamura na temat złożoności prawdziwych operatorów.

Klasycznym odniesieniem do złożoności funkcji rzeczywistych jest książka Ker-I Ko [2]. Rozdział szósty, najnowsza książka Klause Weihrauch [3], omawia także złożoność obliczeń rzeczywistych (ale bardziej skupia się na obliczeniach niż na złożoności).

• [1] Stephen Cook i Bruce Kapron, „Charakterystyka podstawowych możliwych funkcjonałów typu skończonego”, 1990.

• [2] Ker-I Ko, „Złożoność obliczeniowa rzeczywistych funkcji”, 1991.

• [3] Klaus Weihrauch, „Computable Analysis”, 2000.

Model, który opisujesz, jest znany jako model Blum-Shub-Smale (BSS) (także model Real RAM) i rzeczywiście służy do definiowania klas złożoności.

Interesującymi problemy w tej dziedzinie są klasy , N P R , i oczywiście pytanie, czy P R = N P R . Przez P R rozumiemy, że problem można rozstrzygać wielomianowo, N P R oznacza, że ​​problem jest wielomianowo weryfikowalny. Istnieje twardości / kompletności pytania o klasie N P R . Przykładem kompletnego problemu N P R jest problem Q P S , Kwadratowego Układu Wielomianowego, w którym dane wejściowe to prawdziwe wielomiany w$P_R$$NP_R$$P_R$$NP_R$$P_R$$NP_R$$NP_R$$NP_R$$QPS$ zmiennych i P 1 , . . . , P n ⊆ R [ x 1 , . . . , x n ] stopnia co najwyżej 2, a każdy wielomian ma co najwyżej 3 zmienne. Na pytanie, czy istnieje powszechne realnym rozwiązaniem R n , w taki sposób, p 1 ( ) , s 2 ( ) , . . . p n ( a ) = $m$$p_1, ..., p_n$ $\subseteq$ $R[x_1, ..., x_n]$$R^n$$p_1(a), p_2(a), ... p_n(a) = 0$. Jest to kompletny problem $NP_R$

Co jednak ciekawsze, pojawiły się prace nad związkiem między (dowody probalistycznie sprawdzalne), nad rzeczywistością, tj. Klasą P C P R , oraz nad tym, jak odnosi się ona do modeli obliczeń algebraicznych. Model BSS przesuwa się do wszystkich N P w rzeczywistości. Jest to standard w literaturze i dziś wiemy, że N P R ma „przezroczyste długie dowody” i „przezroczyste krótkie dowody”. Przez „przezroczysty długich dowodów” dodaje się zakłada się: N P R znajduje się w p C P R ( P ° l $PCP$$PCP_R$$NP$$NP_R$$NP_R$ . Istnieje również rozszerzenie, które mówi, że „Prawie (przybliżona) wersja krótka” jest również prawdziwa. Czy możemy ustabilizować dowód i wykryć usterki, sprawdzając znacznie mniej (rzeczywistych) komponentów niż n ? Prowadzi to do pytań o istnienie zer dla wielomianów jednowymiarowych zadanych przez program linii prostej. Przez „przezroczyste długie dowody” rozumiemy również$PCP_R(poly, O(1))$$n$

1. „przezroczysty” - tylko do odczytania,$O(1)$

2. długi - wielobiegunowa liczba rzeczywistych składników.

Dowód jest związany z , a jednym ze sposobów spojrzenia na problemy o wartościach rzeczywistych jest to, w jaki sposób można je powiązać z sumą podzbiorów - nawet algorytmy aproksymacji problemów o wartościach rzeczywistych byłyby interesujące - jako optymalizacja - programowanie liniowe, o którym wiemy należy do klasy F P , ale tak, interesujące byłoby sprawdzenie, w jaki sposób przybliżenie może wpłynąć na kompletność / twardość w przypadku problemów N P R. Kolejnym pytaniem byłoby N P R = c o - N P R ? $3SAT$$FP$$NP_R$$NP_R$ $=$ $co\text{-}NP_R$

Myśląc o klasie , zdefiniowano również klasy zliczające, które pozwalają na rozumowanie arytmetyki wielomianowej. Podczas # P jest klasa funkcji f określone na { 0 , 1 } ∞ → N , dla których nie istnieje w czasie wielomianowym Turinga maszyny M i wielomian p z właściwością tego ∀ n ∈ N i x ∈ { 0 , 1 } n , f ( x $NP_R$$\#P$$f$$\{0,1\}^\infty$ $\rightarrow$ $\mathbb{N}$$M$$p$$\forall n$$\in$$\mathbb{N}$$x$$\in$$\{0,1\}^{n}$$f(x)$zlicza liczbę łańcuchów { 0 , 1 } p ( n ), które maszyna Turinga M akceptuje { x , y } . W przypadku rzeczywistości rozszerzamy tę ideę o maszyny addytywne BSS - maszyny BSS, które tylko dodają i mnożą (bez podziałów, bez odejmowania). W przypadku addytywnych maszyn BSS (węzły w obliczeniach pozwalają tylko na dodawanie i mnożenie) model dla # P staje się tym, w którym liczba jest większa niż wektory akceptowane przez maszyny addytywne BSS. Tak więc, klasa licząca to # P i d $y \in$$\{0,1\}^{p(n)}$$M$$\{x,y\}$$\# P$$\#P_{add}$ klasa ta jest przydatna w badaniu liczb Bettiego, a także charakterystyki Eulera.