Środowisko wykonawcze ogranicza się do algorytmów NP całkowitych problemów przy założeniu P ≠ NP

Załóżmy, że . $P\neq NP$

Co możemy powiedzieć o granicach czasu działania wszystkich problemów związanych z NP-zupełnością?

tj. jakie są najostrzejsze funkcje dla których możemy zagwarantować, że optymalny algorytm dla dowolnego problemu z NP zakończony będzie w czasie co najmniej i co najwyżej na wejściu o długości ? $L,U:\mathbb{N}\to\mathbb{N}$ $\omega(L(n))$ $o(U(n))$ $n$

Oczywiście . Również . $\forall c:L(n)=\Omega(n^c)$ $U(n) = O(2^{n^{\omega(1)}})$

Bez założenia , lub jakiegokolwiek innego założenia, które nie jest implikowane przez , czy możemy dać lepsze granice dla ? $QP\neq NP$ $ETH$ $P\neq NP$ $L,U$

EDYTOWAĆ:

Zauważ, że co najmniej jeden z musi być daleki od granic, które tu podałem, ponieważ będąc problemami NPC, problemy te mają między sobą redukcję czasu poli, co oznacza, że jeśli jakiś problem NPC ma optymalny algorytm czasu , wówczas wszystkie problemy mają algorytm (optymalny lub nie) środowiska wykonawczego . $L,U$ $f(n)$ $O(f(n^{O(1)}))$

— RB
źródło

jeśli P NP możemy powiedzieć, że granice środowiska wykonawczego są większe niż jakikolwiek wielomian .... afaik nie, lepsze granice nie są znane ... dużo notacji nie mówi, że ... istnieją superpolinomia-ale- funkcje podwykładnicze np.

\neq

$\neq$

2^{\log n}

$2^{\log n}$

— od

Po pierwsze, jest po prostu liniowy, więc myślę, że masz na myśli który jest znany jako klasa . W pełni zdaję sobie sprawę, że nie oznacza, że żadna funkcja NP-complete będzie działała w czasie wykładniczym, ale nie o to pytam. Na przykład, zakładając , czy jest możliwe, że problem NPC można rozwiązać w , gdzie jest odwrotną funkcją Ackermanna? Notacje są jedynie narzędziem służącym do formalnego wyrażenia mojego pytania ...

2^{\log n}

$2^{\log n}$

2^{p o l y l o g (n)}

$2^{polylog(n)}$

Q P

$QP$

P \neq N P

$P\neq NP$

P \neq N P

$P\neq NP$

2^{l o g (n) \cdot l o g^{*} (n)}

$2^{log(n)\cdot log^*(n)}$

l o g^{*} (n)

$log^*(n)$

— RB,

dzięki za korektę. bardzo mało wiadomo w tej dziedzinie. spróbuj tego pytania NTime (n ^ k) =? DTime (n ^ k) tcs.se

— vzn

@RB Chociaż prawdą jest, że w każdym „możliwym świecie” istnieją dolne i górne granice, które z grubsza znajdują się w obrębie wielomianu, nie jest jasne, jakie granice a priori są możliwe.

— Yuval Filmus

Moja interpretacja tego pytania polega na pytaniu o możliwości w relatywizowanych światach . Załóżmy, że w jakimś relatywizowanym świecie . Czy możemy wydedukować coś nietrywialnego na temat złożoności czasowej problemów związanych z NP-zupełnością? Argument Baker – Gill – Solovay pokazuje, że możemy „zmusić” jakiś problem NP do czasu wykładniczego, więc górna granica podana w pytaniu jest zasadniczo optymalna. $P \neq NP$

Jeśli chodzi o dolną granicę, szkicujemy poniżej dowód, że w odniesieniu do jakiejś wyroczni, . Zakładając, że naszkicowany dowód jest poprawny, możemy go również zastosować do funkcji mniejszych niż , co pokazuje, że dolna granica podana w pytaniu jest również zasadniczo ścisła. $NP = \mathrm{TIME}(2^{O(\log^2 n)})$ $2^{O(\log^2 n)}$

Szkic próbny. Konstruujemy dwa wyrocznie : pierwszy zachowuje się jak -kompletny problem, a drugi implementuje diagonalizację Baker – Gill – Solovay. Łatwo jest spakować obie wyrocznie w jedną wyrocznię. $O_1,O_2$ $\mathrm{TIME}(2^{O(\log^2 n)})$

Wyrocznia składa się ze wszystkich par dzięki czemu jest wyrocznią maszyną Turinga, która akceptuje w czasie wykonywania po uzyskaniu dostępu do wyrocznie ograniczone do danych wejściowych o długości maksymalnie . (To nie jest okrągła definicja). $O_1$ $\langle M, x \rangle$ $M$ $x$ $2^{2^{\sqrt{\log |x|}}}$ $O_1,O_2$ $2^{\sqrt{\log |x|}}$

Wyrocznia jest zdefiniowana w taki sam sposób, jak wyrocznia zdefiniowana w Baker – Gill – Solovay: dla każdej taktowanej wyroczni maszyny Turinga pracującej w czasie , znajdujemy pewne dane wejściowe długość która jest „nietknięta”, uruchom na dla kroków, a dla każdego zapytania do o rozmiarze zaznaczamy, że to wejście nie jest w (w przypadku innych zapytań zaznaczamy również, że wejścia tam nie ma , chyba że już zdecydowaliśmy, że jest w wersji ). Zapytania do są obsługiwane podobnie (jak dorozumiane zapytania do $O_2$ $M$ $T = 2^{o(\log^2 n)}$ $n$ $M$ $1^n$ $T$ $O_2$ $n$ $O_2$ $O_2$ $O_1$ $O_1,O_2$ mniejszego rozmiaru, obsługiwane rekurencyjnie); zauważ, że takie zapytania nigdy nie wspominają o ciągach o długości w , ponieważ . Jeśli maszyna zaakceptuje, wszystkie pozostałe ciągi o długości w jako brakujące, w przeciwnym razie wybieramy jakiś ciąg o długości i umieszczamy go w . $n$ $O_2$ $2^{\sqrt{\log T}} < n$ $n$ $O_2$ $n$ $O_2$

Klasa składa się ze wszystkich programów działających w czasie , wykonując zapytania do o rozmiarze . Klasa ma postać , gdzie , a więc jest zawarte w klasie wszystkich programów działających w czasie i wykonujących zapytania Oracle o rozmiarze . Ten ostatni jest zawarty w , ponieważ możemy użyć do podjęcia decyzji. To pokazuje że $P^{O_1,O_2}$ $2^{2^{O(\sqrt{\log n})}}$ $O_1,O_2$ $2^{O(\sqrt{\log n})}$ $NP^{O_1,O_2}$ $x \mapsto \exists |y|<n^C \varphi(x,y)$ $\varphi \in P^{O_1,O_2}$ $2^{n^C}$ $2^{O(\sqrt{\log n})}$ $\mathrm{TIME}(2^{\log^2 n^C})^{O_1,O_2}$ $O_1$ $NP^{O_1,O_2} \subseteq \mathrm{TIME}(2^{O(\log^2 n)})^{O_1,O_2}$ .

Dla drugiego kierunku niech będzie językiem, który składa się z dla każdego tak że zawiera jakiś ciąg długości . Konstruując , , podczas gdy wyraźnie . To pokazuje, że . $L$ $1^n$ $n$ $O_2$ $n$ $O_2$ $L \notin \mathrm{TIME}(2^{o(\log^2 n)})^{O_1,O_2}$ $L \in NP^{O_1,O_2}$ $NP^{O_1,O_2} = \mathrm{TIME}(2^{O(\log^2 n)})^{O_1,O_2}$

— Yuval Filmus
źródło

Muszę przyznać, że nie w pełni zrozumiałem twoją odpowiedź, ale jeśli, jak wspomniałeś, jakiś NP-zupełny problem można rozwiązać tylko w , wtedy wszystkie inne problemy NPC są również możliwe do rozwiązania tylko w , ponieważ występuje w nich skrócenie czasu poli z , co oznacza, że w przeciwnym razie miałbyś lepszy algorytm dla . Oznacza to na przykład i prawda? czego mi brakuje?

Π

$\Pi$

Ω (2^{n^{c}})

$\Omega(2^{n^c})$

Ω (2^{n^{Ω (1)}})

$\Omega(2^{n^{\Omega(1)}})$

Π

$\Pi$

Π

$\Pi$

Q P \neq N P

$QP\neq NP$

E T H

$ETH$

— RB,

Cóż, to nie oznacza , ale wygląda na to, że może oznaczać .

E T H

$ETH$

Q P \neq N P

$QP\neq NP$

— RB

Niczego nie brakuje. Istnieje świat relatywizowany, w którym ETH jest prawdą. Istnieje inny relatywizowany świat, w którym P = NP, a zatem w szczególności ETH jest fałszem.

— Yuval Filmus

Ale nie we wszystkich zrewitalizowanych światach, w których , jest również prawdą, prawda? Istnieje prawdopodobieństwo, że . Z tego, co zrozumiałem z twojej odpowiedzi, jeśli istnieje problem NPC, którego dolna granica jest wykładnicza, i zastanawiam się, dlaczego to prawda.

P \neq N P

$P\neq NP$

Q P \neq N P

$QP\neq NP$

P ⊊ Q P = N P

$P\subsetneq QP = NP$

P \neq N P

$P\neq NP$

— RB

W mojej odpowiedzi (rzekomo) podam relatywizowany świat, w którym . Inny relatywizowany świat ma . W jeszcze innych relatywizowanych światach . Jeśli chodzi o , nie twierdzę o tym nic.

N P = T I M E (n^{O (\log n)})

$NP = \mathrm{TIME}(n^{O(\log n)})$

N P = T I M E (2^{n^{O (1)}})

$NP = \mathrm{TIME}(2^{n^{O(1)}})$

P = N P

$P=NP$

Q P

$QP$

— Yuval Filmus

Środowisko wykonawcze ogranicza się do algorytmów NP całkowitych problemów przy założeniu P ≠ NP

Bez założenia , lub jakiegokolwiek innego założenia, które nie jest implikowane przez , czy możemy dać lepsze granice dla ?E T H P ≠ N P L , UQP≠NPQP≠NPQP\neq NPETHETHETHP≠NPP≠NPP\neq NPL,UL,UL,U

Bez założenia , lub jakiegokolwiek innego założenia, które nie jest implikowane przez , czy możemy dać lepsze granice dla ? $QP\neq NP$ $ETH$ $P\neq NP$ $L,U$